Date:         Tue, 25 Sep 2001 13:37:18 -0400
Reply-To:     Reynald LERCIER <>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <>
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)


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.


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.


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,


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,, Reynald LERCIER (CELAR, Rennes, France,

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

[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.