Date:         Tue, 25 Sep 2001 13:37:18 -0400
Reply-To:     Reynald LERCIER <lercier@club-internet.fr>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <lercier@club-internet.fr>
Subject:      Discrete logarithms in GF(2^n)

We are pleased to announce a new record for the discrete logarithm
problem. We were able to compute discrete logarithms in
GF(2^521). This was done in one month on a unique 525MHz
quadri-processors Digital Alpha Server 8400 computer. The approach
that we followed is a careful implementation of the general Function
Field Sieve as described from a theoretical point of view by Adleman
[Ad94].

As far as we know, the largest such computation previously done was
performed in GF(2^401) [GoMc92] using an algorithm due to Coppersmith
[Co84]. An attempt for GF(2^503) is also described in [GoMc92], but it
seems that the linear algebra step was too hard to be
completed. Finally, another attempt that we are aware of seems to be a
computation in GF(2^607) with Coppersmith's algorithm, but we have no
more detail about it [Th01].

The software we used is an adaptation of our GF(p) code [JoLe00] to
the characteristic 2 case taking advantage of a generic software based
on a Finite Field C Library called ZEN. It turns out, in addition to
some specific algorithmic improvement due to the characteristic 2
case, that most of the ideas developed for the characteristic p case
can be applied in GF(2^n). A preprint is in preparation [JoLe01].

Precisely, let

GF(2^521) = GF(2)[t]/
 (t^521+t^519+t^518+t^517+t^514+t^513+t^512+t^511+t^510+t^509+t^507+t^506+
  t^504+t^501+t^499+t^497+t^496+t^494+t^493+t^490+t^489+t^488+t^486+t^481+
  t^479+t^478+t^475+t^474+t^473+t^471+t^469+t^466+t^465+t^464+t^463+t^460+
  t^455+t^453+t^452+t^450+t^449+t^447+t^445+t^444+t^443+t^442+t^441+t^439+
  t^437+t^435+t^433+t^432+t^426+t^425+t^424+t^423+t^419+t^416+t^415+t^414+
  t^413+t^408+t^404+t^402+t^401+t^399+t^398+t^397+t^396+t^393+t^392+t^388+
  t^387+t^386+t^385+t^383+t^379+t^377+t^376+t^371+t^370+t^367+t^366+t^364+
  t^361+t^349+t^345+t^344+t^343+t^341+t^338+t^336+t^335+t^333+t^330+t^329+
  t^328+t^327+t^323+t^321+t^315+t^313+t^311+t^310+t^309+t^304+t^300+t^299+
  t^298+t^295+t^293+t^292+t^288+t^285+t^283+t^275+t^272+t^271+t^270+t^267+
  t^264+t^258+t^256+t^255+t^253+t^250+t^247+t^246+t^241+t^238+t^237+t^236+
  t^235+t^233+t^232+t^230+t^229+t^227+t^223+t^220+t^219+t^218+t^215+t^214+
  t^212+t^211+t^209+t^201+t^198+t^197+t^193+t^192+t^191+t^190+t^188+t^182+
  t^179+t^176+t^175+t^173+t^172+t^169+t^168+t^167+t^165+t^160+t^159+t^158+
  t^156+t^154+t^153+t^150+t^149+t^147+t^146+t^145+t^144+t^139+t^137+t^136+
  t^135+t^134+t^129+t^128+t^125+t^124+t^121+t^118+t^117+t^116+t^115+t^114+
  t^113+t^109+t^104+t^102+t^101+t^100+t^99+t^94+t^86+t^85+t^83+t^82+t^81+
  t^77+t^76+t^75+t^74+t^73+t^72+t^70+t^69+t^67+t^64+t^61+t^60+t^58+t^57+
  t^56+t^52+t^51+t^49+t^44+t^42+t^39+t^37+t^35+t^33+t^29+t^28+t^26+t^25+
  t^24+t^22+t^20+t^19+t^14+t^13+t^10+t^5+t^3+1)

and

  g = t.

Let F(x) be the mapping defined from the set of integers to GF(2)[t]
which sends an integer x to a polynomial F(x) such that substituting t
by 2 in F(x) yields x. For instance, F(5) = t^2+1.

Let

  e(t) = F(\lfloor 2^519 \exp(1) \rfloor) = t^520+t^518+ ... +t^6+t^3,

 pi(t) = F(\lfloor 2^519 \pi \rfloor)     = t^520+t^519+ ... +t^6+t^3+1.

Then,

  e(t)     = g^2632477621938341298849947024285383602893174070932731771900256\
               0095841802532546548170764837586429284565024547468908202520438\
               76734626779920800953806109457874358,

  pi(t)    = g^5475291480121133585788840019440488343960416954316922618373225\
               4379376071733986861125955339801609047087900511385882090917394\
               55561530487613513767198209433496844,

and, similarly,

e(t)+pi(t) = g^4159201401120253179205437750401930764399753767149916610720425\
               4336716803038673658116807896648515062724652393078628468989571\
               89950632165222399100568185398518167.

As for the large characteristic case, this computation was done in three steps:
  _ the sieving step,
  _ the linear algebra,
  _ the final computation of individual logarithms.

Sieving:
--------

The sieving step consisted in finding couples (a(t),b(t)) \in GF(2)[t]^2
such that the divisor of the function (a(t)*u+b(t)) is of smooth norm
in the so-called ``right'' algebraic function field defined by a curve
of genus 0 given by

   u^5 + u + F(3)

and such that the factorization of the polynomial

              F(240821905985569136136) * a(t) +
   F(34953265866511665874758795389039) * b(t)

is smooth too.

The sieving was done efficiently following a ``sieving by vector''
with ``special-q'' technique classically used in the large
characteristic case.  It yields many linear equations between
``logarithms of ideals'' of norms smaller than F(6157313) (300000-th
irreducible polynomial over GF(2)) in the left field and of norms
smaller than F(4194307) (210870-th irreducible polynomial) in the
right field.

After a 3 weeks computation on a quadri-processors alpha server 8400
computer, we obtained 472121 equations with 450940 unknowns.

Linear algebra:
---------------

The linear algebra was further divided in two phases.

We first applied structured Gaussian eliminations to reduce our system
to 197039 equations in 196939 unknowns with 12220108 non null entries
[LaOd91, JoLe00]. Time needed for this on only one processor was about
one hour.

Then, the critical phase was the final computation via Lanczos's
algorithm [GoLo89]. Our parallelized version of this algorithm took 10
days over 4 processors. At the end, we had ``logarithms for ideals''
of small norms. As a consequence, we had logarithms for small
irreducible polynomials.

For instance,

      F(3) = g ^ 9468157715212229407617517359865032460621888852201905263910\
                 8014879989858843458649522013207549688251336155264179231636\
                 5389142863458255063795516109214621940159,

      F(7) = g ^ 4099453203357757668284443933632134015543756038796071121488\
                 0627918982361730130023913248564073810794905281894307814220\
                 62155331435951419903283877277822018761891,

     F(11) = g ^ 5993393783882148815449649153225147145392118903526654848802\
                 3002525852428492484287946073847933216844736572675883441815\
                 48639112359865833736964986527249492347548,

     F(13) = g ^ 2970623240405268942772078849793030115355234738306410306089\
                 4070723309597937692641825394305454861135524387715335257436\
                 94515204664884894850566138301634815009693,

           .

           .

           .

F(4194253) = g ^ 4079138049200743992418711990400391098564834260917757444528\
                 8207760275309787006774877156017081053556941109636212184673\
                 07521054150349999295225433479794718437954.

Individual Logarithms:
----------------------

We found in few hours, two polynomials,

   num(t) = F(416505357177365) * F(13902762769) * F(2209798967) *
            F(143323807) * F(80322227) * F(27405533) * F(14596985) *
            F(406927) * F(12367) * F(1717) * F(1051) * F(117) * F(2)^4,

and

   den(t) = F(72489510916391) * F(8084941431379) * F(48967193557) *
            F(222438663) * F(185273873) * F(863301) * F(530537) *
            F(21729) * F(2693) * F(1033) * F(607) * F(253) * F(59) *
            F(7) * F(3),

such that

   F(4194253)^43*e(t) = num(t)/den(t) in GF(2^521).

Then, using special-q descents, computing discrete ``logarithms for
the ideals'' of norms larger than F(6157313) in the left algebraic
field was (thanks to a one hour computation for each ideal, on a
unique processor) equivalent to compute discrete ``logarithms for
ideals'' of norms larger than those of the factor basis in the right
algebraic function field. Time needed for computing the corresponding
discrete logarithms was at most one hour for each on a unique
processor.

So, as a conclusion, time that we need for computing discrete
logarithms in GF(2^521) on a 525 MHz quadri-processor alpha server
8400 computer is approximatively 12 hours for each, once the sieving
step (21 days) and the linear algebra step (10 days) is performed.


Antoine JOUX    (DCSSI, Issy les Moulineaux, France, Antoine.Joux@ens.fr),
Reynald LERCIER (CELAR, Rennes, France, lercier@celar.fr).


References:
===========

[JoLe01]  A. Joux and R. Lercier, ``The function field sieve in
          GF(2^n)'', Preprint.

[Th01]    E. Thome, ``Computing discrete logarithms over GF(2^607)'',
          submitted at Asiacrypt 2001.

[JoLe00]  A. Joux and R. Lercier, Improvements to the general Number
          Field Sieve for discrete logarithms in prime fields, acceped
          for publication at Math. of Comp., 2000. Preprint
          available at http://www.medicis.polytechnique.fr/~lercier.

[Ad94]    L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture
          Notes in Math., 1994, volume 877.

[GoMc92]  D.M. Gordon and K.S. McCurley, ``Massively Parallel Computation
          of Discrete Logarithms''. Advances in Cryptology, CRYPTO'92,
          Lecture Notes in Computer Science, 1992, volume 740.

[LaOd91]  B.A. Lamacchia and A.M. Odlyzko, Computation of discrete
          logarithm in prime fields, Designs, Codes and Cryptography,
          1991, volume 1, pages 47-62.

[GoLo89]  G.H. Golub and C.F. van Loan, Matrix computations, chapter 9,
          The John Hopkins University Press, 1989, Mathematical
          Sciences.

[Co84]    D. Coppersmith, ``Fast Evaluation of discrete logarithms in fields
          of characteristic 2''. IEEE Transactions on Information Theory,
          1984, volume 30, pages 587-594.