Date:         Fri, 23 Sep 2005 18:18:24 -0400
Reply-To:     Antoine Joux 
Sender:       Number Theory List 
From:         Antoine Joux 
Subject:      Discrete logarithms in GF(2^607) and GF(2^613)

Thursday, September 22nd, 2005. We are pleased to announce a new record for the discrete logarithm problem over GF(2^n). Using the function field sieve of Adleman [Ad94], we were able to compute discrete logarithms in GF(2^607) and GF(2^613). The first computation gives an interesting comparison between the function field sieve and Coppersmith's algorithm since the same field finite was already addressed by Thome using the later algorithm. As far as we know, the largest such computation previously done was performed in GF(2^607) by Thome using Coppersmith's algorithm [Thome02]. The timings reported by Thome (approx. 20000 MIPS years) are approximatively 12 times larger than the constated runtime during our FFS experiment (approx. 1500 MIPS years). The software we used is an adaptation of our GF(p) code to the characteristic 2 case taking advantage of a generic software based on a Finite Field C Library called ZEN. In the characteristic 2 case, we know that very efficient polynomials can be constructed, thus giving the algorithm the same asymptotic complexity as the SNFS, see [AdHu99] and [JoLe02]. It also turns out, that most of the ideas developped for the characteristic p case can be applied. In particular, we used the same structured gaussian elimination procedure than in the 130 digits discrete logarithm computation announced here in June [JoLe05]. The two computations were done using different computers. For GF(2^607), we used a single 1.15GHz 16-processors HP AlphaServer GS1280 computer during one month. For GF(2^613), we used four 16-processors nodes of the itanium 2 based Bull computer Teranova during 17 days (1.3GHz CPUs). Details of the 607 bits computation: ------------------------------------ Let, GF(2^607) = GF(2)[t]/ (t^607+t^605+t^494+t^493+t^492+t^490+t^489+t^488+t^486+t^155+t^153+t^151+ t^149+t^143+t^141+t^139+t^137+t^123+t^121+t^42+t^41+t^40+t^33+t^32+t^29+ t^28+t^21+t^20+t^18+t^10+t^9+t^8+t^6+t^5+t^4+t^2+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 pi(t) = F(\lfloor 2^605 \pi \rfloor) = t^606+t^605+ ... +t^4+t^2. Then, pi(t) = g^194891399758968486429687093757270550092585346683729020126\ 283742527056226784304085164731800423582020004466178421521\ 409573307372675772079931586693537551194866503272438476718\ 291852872030. 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(5) and such that the factorization of the polynomial a(t) + F(2^121+2^8+2^7+2^5+2^4+1) * 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(22395195) (1000000-th irreducible polynomial over GF(2)) in the left field and of norms smaller than F(16777243) (765925-th irreducible polynomial) in the right field. After a 18 days computation on a 1.15 GHz 16-processors HP AlphaServer GS1280 computer, we obtained 1898338 useful equations with 1556351 unknowns. Linear algebra: --------------- The linear algebra was further divided in two phases. We first applied our new structured Gaussian eliminations to reduce our system to 365928 equations in 364927 unknowns with 104312947 non null entries. Time needed for this on only one processor was less than 15 minutes on only one processor. Then, the critical phase was the final computation via Lanczos's algorithm. Our parallelized version of this algorithm took 17 days over 16 processors. At the end, we had ``logarithms for ideals'' of small norms and, as a consequence, we had logarithms for small irreducible polynomials. For instance, F(3) = g ^ 1060949212859562222262493702624296695723135234776723302\ 00666223675011082943476527357064661792736790795355204136627\ 16562898663665513345829851531181693190003317157153674790128\ 8957967953, F(7) = g ^ 2520048934917069779831062050295651583064497255985365264\ 21876277776038590761926757324360558160692922785915155428024\ 08816416151878677859473587741836141279445015081142869326983\ 907031635, F(11) = g ^ 5285790861846577957804828942375119662184718686715282567\ 66962997896082262912436049612433227319619341896423330634824\ 97625024355701766762338498042682870871941097811486539693192\ 6276790609, F(13) = g ^ 2776685678422577662147422896753523755481580447535557166\ 59418478534534170093508097298762471177568721780650729614539\ 28534740840511470429127281769449576012561370910747459417754\ 384466, ... F(22395195) = g^328336750529106084982429881581245161065548886074034972647\ 311385749111490214992897570687009560335784476212035915899\ 760943330530210741077758356175062319253271523700882159349\ 834819269812. Individual Logarithms: ---------------------- We found in less than one hour, two polynomials, num(t) = F(9162372248009269) * F(2833280310146019) * F(981656501891) * F(39549926607) * F(16870036327) * F(2911549) * F(39805) * F(28963) * F(21365) * F(18357) * F(13753) * F(2601) * F(7) and den(t) = F(1246475253358441) * F(287847350809) * F(13015023387) * F(32693327483) * F(1783705623) * F(239925077) * F(21745087) * F(5481635) * F(2898329) * F(1863) * F(721) * F(253) * F(11)^2 * F(3) * F(2)^4 such that F(22395195)^27*pi(t) = num(t)/den(t) in GF(2^607). Then, using special-q descents, computing discrete ``logarithms for the ideals'' of norms larger than F(22395195) in the left algebraic field was equivalent to compute discrete ``logarithms for ideals'' of norms larger than those of the factor basis in the right algebraic function field. This took only a few minutes of CPU time. The time needed for computing an individual discrete logarithms in GF(2^607) on one 1.15 GHz 16-processors HP AlphaServer GS1280 computer is under an hour, once the sieving step (18 days) and the linear algebra step (17 days) is performed. Details of the 613 bits computation: ------------------------------------ Let GF(2^613) = GF(2)[t]/ (t^613+t^611+t^610+t^499+t^497+t^495+t^492+t^491+t^490+t^489+ t^366+t^252+t^249+t^248+t^247 +t^245+t^157+t^155+t^154+t^145+ t^143+t^142+t^141 +t^139+t^137+t^135+t^134+t^132+t^130+t^129+ t^128 +t^127+t^126+t^124+t^122+t^43+t^41+t^39+t^36+t^35+t^34+ t^33+t^31+t^29+t^25+t^23+t^22+t^21+t^19+t^15+t^14+t^12+ t^7+t^5+t^4+t+1) and g = t. Let F(x) be as defined above. Let e(t) = F(\lfloor 2^611 \exp(1) \rceil) = t^612+t^610+ ... +t^5+t^3. Then, e(t) = g^90540166494671221719626670665040194356925139180273182043355 293265810227816669720315781123274014763220199558782053577040234 12586910522044360597168220282140625205497011520180866370303882 The computation used the same steps as above. Sieving: -------- The ``right'' algebraic function field is defined by u^5+u^4+u^2+(t^3+t+1). We also require that a(t)+ (t^122+t^8+t^5+t^4+t^3+t)*b(t) is smooth. The bound for small ideal was F(33554432) (1465020-th irreducible polynomial over GF(2)) on both sides. After a 4 days computation on four 16-processors nodes, we obtained 5387415 useful equations with 2879101 unknowns. Linear algebra: --------------- We first applied our new structured Gaussian eliminations to reduce our system to 403178 equations in 402154 unknowns with 152161682 non null entries. Time needed for this on only one processor was about 15 minutes on a single processor. Our parallelized version of the Lanczos' algorithm then took 13 days over four 16-processors nodes. Here is a sample of the result: F(3) = g ^ 2063740429642602377228525818500941651870240635044800 4911929146998757589544076526162419233825266927893750 0828663539095933795101419292210327527910101443768887 10317433660025156726402045497 F(7) = g ^ 1970226238871415159139256592389766065573453254436002 5678333053786726818232388688740594435045036580994749 3179380666581915298804648319648952834860017803406472 55636703755773749643637310553 F(11) = g ^ 1376760539080237423601908777579676277131772106336408 9507060669784404491938398624603130505166785033291547 8815645007826483954728577128443183885130690419778825 26434726822099690509507248154 F(13) = g ^ 3442750725293094917838196293196348614623633274655312 3145305274666669398896947205168326407692963984901532 0466692419569570138376558148427721257268715811356360 2241411454308361749120771972 ... F(33553757) = g ^ 1406085348152248639989295095399521815262803460302160 4894203923165228201314849853906320268001645079258250 2228211729452876381481958191872037119864775142445006 47199086198854444723241177549 Individual Logarithms: ---------------------- We found in less than one hour, two polynomials, num(t) = F(15506735) * F(6109055) * F(31475) * F(1835) * F(19) * F(7) * F(8167719318131749415) * F(62627218263025061503) * F(49277132941) * F(6893932779863494865230135) and den(t) = F(33513655) * F(6441771) * F(375235) * F(82597) * F(57397) * F(1053) * F(971) * F(193) * F(25) * F(2)^2 * F(4074544069) * F(167141529695) * F(197958190319) * F(234985401838936862111309147) such that F(33553757)^22*e(t) = num(t)/den(t) in GF(2^613). We concluded the computation by special-q descent as above. Antoine JOUX (DGA & Universite de Versailles, France, antoine.joux(at)m4x.org), Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org). References: =========== [Ad94] L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture Notes in Math., 1994, volume 877. [AdHu99] L.M. Adleman and M.A. Huang. Function field sieve method for discrete logarithm over finite fields. Information and computation, 1999, volume 151, pages 5-16. [Co84] D. Coppersmith, ``Fast Evaluation of discrete logarithms in fields of characteristic 2''. IEEE Transactions on Information Theory, 1984, volume 30, pages 587-594. [JoLe02] A. Joux and R. Lercier, The function field sieve is quite special. ANTS-V, LNCS 2369, pages 431--445, 2002. [JoLe05] A. Joux and R. Lercier, ``Discrete logarithms in GF(p)'', Saturday, June 18th 2005. NMBRTHRY Mailing List. [Thome02] E. Thome, ``Discrete logarithms in GF(2^607)'', Saturday, Feb. 23th 2002. NMBRTHRY Mailing List.