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