February 21, 2002. This note was originally posted to the NMBRTHRY mailing list. You can find it here



Discrete Logarithms in GF(2^607)

Discrete Logarithms in GF(2^607)

We are pleased to announce that we have been able to extend the record for computing discrete logarithms in fields of characteristic 2 to the size of 607 bits. The previous record for such computation was GF(2^521) [JoLe01]. Before that, Gordon and McCurley computed logs in GF(2^403), and did most of the job to compute logs in GF(2^503) [GoMc93].

We did the discrete logarithm computation using Coppersmith's index-calculus algorithm [Co84]. This algorithm has sub-exponential complexity (L[1/3]) with respect to the size of the field (here, 607). The algorithm proceeds through three steps.

1) [Sieving] A factor base is chosen, consisting of all polynomials of degree less than a given bound, and we collect relations involving the logarithms of these polynomials.

2) [Linear algebra] We solve the linear system resulting from these relations, and deduce the logarithms of all the elements in the factor base.

3) [Individual logs] We express the log of any given polynomial as a linear combination of the logs of the elements of the factor base, thereby obtaining the result.

A more detailed account of our computations is in [Th01b]. We give a brief summary.

Algorithm and figures.

The computations were done modulo the irreducible polynomial f(X)=X^607+X^9+X^7+X^6+X^3+X+1 ; The chosen factor base was made up of all irreducible polynomials of degree up to 23, for a total of 766,150 factor base elements.

Step 1) The procedure used to collect relations is Coppersmith's procedure, augmented with the so-called double large prime variation.

- Select pairs of polynomials (A(X), B(X)), deg(A)<=21, deg(B)<=28 such that: A(X) and B(X) are coprime C(X) = A(X)*X^152 + B(X), and D(X) = C(X)^4 mod f, together, have factorizations that do not contain more than two factors of degree larger than 23. According to this number of ``large primes'' being 0, 1, or 2, we refer to the resulting relation D(X)=C(X)^4 as being ``full-full (ff)'', ``partial-full (pf)'', or ``partial-partial (pp)''

- Match the ``pf'' and ``pp'' relations together in order to obtain additional full relations.

- stop when sufficiently many relations are available (more than the size of the factor base).

This step is highly distributable and was run over a period of one year using idle time on about 100 computers (desktop PCs, mainly) at different places (see acknowledgements below).

At the end of step 1), we exhausted more than 50% of the search space for A(X) and B(X) mentioned above. We obtained 1,033,593 relations, 815,726 of them being derived from the combination of ``pf'' and ``pp'' relations (the total number of relations, including partial ones, was 60,346,286). On average, relations involved 67.7 factor base elements. The most complex combination of pf and pp relations involved 40 such relations.

Step 2) is a linear algebra computation, taking place over the ring of integers modulo 2^607-1.

First, we used a structured gaussian elimination procedure, as described in [PoSm92], in order to reduce the size of our linear system. Starting with a 1,033,593 x 766,150 matrix, of average row weight of 67.7, we ended up with a 480,108 x 480,108 matrix, with average row weight 104.8 ; 400 megabytes were necessary to hold this matrix in memory.

Schedule time for the structured gaussian elimination was roughly one day CPU on an alpha EV67 667MHz computer.

Then, we found an element of the null space of this matrix using the block Wiedemann algorithm [Co94]. This algorithm is a generalization of Wiedemann's algorithm, allowing partial distribution of the work across several computers (within this algorithm, the generalization of the Berlekamp-Massey algorithm remains sequential. However this step has been improved by [Th01a]). We have set up the parameters of this algorithm to allow the concurrent use of eight machines, taking furthermore advantage of the SMP capability of the machines we had access to, in order to cut down on the time needed to do the crucial matrix-times-vector multiplication.

We did this linear algebra step twice, because a mistake voided our results on the first try. The schedule time was two months, but using an heterogeneous pool of computers, none of them working at full speed. If we try to express the time required to do this linear algebra step using the latest resource we had access to, which is a cluster of six 4-cpu alpha EV68 833MHz computers, we would obtain a computation time of four weeks.

Using the result of the linear algebra, we back-substituted the known logs in the relations that we had. This eventually yielded 766,009 logs of the elements of the factor base (that is, we only missed 141 logs). After that, in order to improve the efficiency of the next step, we tried to derive as much knowledge as we could on the logs of the polynomials of degree 24 and 25, which were ``just above'' the factor base. Using the same kind of back-substitution, we were eventually able to obtain the log of 80% of the elements of this ``extended'' factor base (up to degree 25).

Step 3) is essentially the expression of the log of some given polynomial as a linear combination of the known logs. The procedure we used is in the spirit of what Coppersmith originally described in [Co84]. The two main ingredients are the half-gcd algorithm, and the special q sieving.

Although step 3 is subexponential, as the two preceding steps, the associated constant is much smaller. Therefore, it is not surprising to see that three hours cpu on an alpha EV67 667MHz are enough to obtain one given log.

Acknowledgements.

A number of institutions provided CPU time for this computational effort. Our thanks go to all of them.

The bulk of the sieve computations was done at Ecole Polytechnique, Palaiseau, France. Gérard Guillerm granted us access to the student computer clusters which were idle during term breaks, turning these clusters into a very effective and helpful task force. Many jobs were run also at UMS MEDICIS, where we would like to thank Joël Marchand and Teresa Gomez-Diaz for their patience and responsiveness to all sorts of problems. Also, still at Ecole Polytechnique, our own computers at LIX did more than a fair amount of the sieving, as well as the subsequent large-prime matching.

The block Wiedemann algorithm involved resources from different places. SMP scalability, and portability of the code were tested with the aid of the Compaq TestDrive program, and we thank Tim Regan there for letting our jobs run although those jobs were putting the machines under high pressure, and even brought some of them down a couple of times. Resources used for the linear algebra computation also included computers from LIX, UMS MEDICIS, and lately from the IDRIS computing faciliy, Orsay, France. We would like to thank Victor Alessandrini at IDRIS for suggesting, and allowing, that we use the IDRIS computers for our purpose: We were delighted to be able to use the cluster of six 4-cpu alphas there, which helped greatly to finish the linear algebra computations.

Computation of individual logs was entirely done at LIX.

References.

[Co84] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inform. Theory, IT-30(4):587--594, July 1984.

[Co94] D. Coppersmith, Solving linear equations over GF(2) via block Wiedemann algorithm. Math. Comp., 205(62):333--350, Jan. 1994

[Ga00] S. Galbraith, On the efficiency of elliptic curves arising in French literature. In Journal of Craptology, Sept. 2001. http://www.mat.dtu.dk/people/Lars.R.Knudsen/crap.html

[GoMc93] D. M. Gordon and K. S. McCurley, Massively parallel computation of discrete logarithms. In E. F. Brickell (ed), Proc. CRYPTO'92, vol. 740 in Lect. Notes Comput. Sci., pp 312--323. Springer, 1993.

[JoLe01] A. Joux and R. Lercier, Discrete logarithms in GF(2^n), e-mail to the NMBRTHRY mailing list, Sept. 2001. Archive available at http://listserv.nodak.edu/archives/nmbrthry.html

[PoSm92] C. Pomerance and J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes. In Experimental Mathematics, 2(1):89--94, 1992.

[Th01a] E. Thomé, Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm. In B. Mourrain (ed), Proc. ISSAC '2001, pp 323--331. ACM Press, 2001.

[Th01b] E. Thomé, Computation of discrete logarithms in GF(2^607). In C. Boyd and E. Dawson (eds), Proc. ASIACRYPT '2001, vol. 2248 in Lect. Notes Comput. Sci., pp 107--124. Springer, 2001.

See also: http://www.lix.polytechnique.fr/Labo/Emmanuel.Thome/

Verification data.

Let K be the splitting field over GF(2) of the irreducible polynomial f(X)=X^607+X^9+X^7+X^6+X^3+X+1

Let P(X) be the polynomial over GF(2) with the following binary representation (LSB first):

0000000: 54 65 73 20 79 65 75 78 20 73 6f 6e 74 20 73 69
0000010: 20 70 72 6f 66 6f 6e 64 73 20 71 75 27 65 6e 20
0000020: 6d 27 79 20 70 65 6e 63 68 61 6e 74 20 70 6f 75
0000030: 72 20 62 6f 69 72 65 0a 4a 27 61 69 20 76 75 20
0000040: 74 6f 75 73 20 6c 65 73 20 73 6f 6c 65 69 6c 73
0000050: 20 79 20 76 65 6e 69 72 20 73 65 20 6d 69 72 65
0000060: 72 0a

This is the ASCII encoding of an excerpt of Louis Aragon's ``Les yeux d'Elsa'':

Tes yeux sont si profonds qu'en m'y penchant pour boire
J'ai vu tous les soleils y venir se mirer

We can verify that P(X) is congruent to X^l mod f(X), where:

l:=47891146166194669675367248797495517594707810094989740173770621404397405\
      43970903739336135936970649474601608959493147659399495433873340533222\
      59124498269177310650885248209789392038650635;

Code for verifying this with MAGMA is:

KP<X>:=PolynomialAlgebra(GF(2));
f:=X^607+X^9+X^7+X^6+X^3+X+1;
K<t>:=ext<GF(2)|f>;
P:= X^779 + X^777 + X^774 + X^773 + X^772 + X^769 + X^766 + X^765 + X^762 + 
    X^760 + X^758 + X^757 + X^756 + X^753 + X^750 + X^749 + X^747 + X^744 +
    X^742 + X^741 + X^739 + X^738 + X^736 + X^733 + X^726 + X^725 + X^722 +
    X^720 + X^718 + X^717 + X^716 + X^713 + X^712 + X^709 + X^702 + X^701 +
    X^700 + X^697 + X^694 + X^693 + X^691 + X^688 + X^686 + X^685 + X^683 +
    X^682 + X^681 + X^678 + X^677 + X^674 + X^672 + X^670 + X^669 + X^668 +
    X^666 + X^665 + X^661 + X^654 + X^653 + X^652 + X^651 + X^648 + X^645 +
    X^638 + X^637 + X^636 + X^633 + X^632 + X^630 + X^629 + X^627 + X^626 +
    X^622 + X^621 + X^619 + X^616 + X^614 + X^613 + X^610 + X^608 + X^606 +
    X^605 + X^603 + X^602 + X^598 + X^597 + X^595 + X^594 + X^593 + X^592 +
    X^590 + X^589 + X^588 + X^585 + X^584 + X^581 + X^574 + X^573 + X^572 +
    X^569 + X^568 + X^566 + X^565 + X^562 + X^560 + X^558 + X^557 + X^555 +
    X^554 + X^549 + X^542 + X^541 + X^540 + X^537 + X^536 + X^534 + X^533 +
    X^532 + X^530 + X^528 + X^526 + X^525 + X^523 + X^522 + X^521 + X^520 +
    X^518 + X^517 + X^516 + X^514 + X^509 + X^502 + X^501 + X^500 + X^498 +
    X^496 + X^494 + X^493 + X^492 + X^490 + X^489 + X^485 + X^478 + X^477 +
    X^475 + X^472 + X^470 + X^469 + X^464 + X^461 + X^458 + X^457 + X^456 +
    X^454 + X^451 + X^449 + X^443 + X^441 + X^438 + X^437 + X^434 + X^432 +
    X^430 + X^429 + X^428 + X^425 + X^422 + X^421 + X^419 + X^416 + X^414 +
    X^413 + X^411 + X^410 + X^409 + X^408 + X^406 + X^405 + X^401 + X^397 +
    X^390 + X^389 + X^388 + X^385 + X^382 + X^381 + X^380 + X^378 + X^376 +
    X^374 + X^373 + X^371 + X^370 + X^369 + X^368 + X^366 + X^365 + X^364 +
    X^357 + X^350 + X^349 + X^348 + X^346 + X^342 + X^341 + X^339 + X^338 +
    X^337 + X^334 + X^333 + X^328 + X^326 + X^325 + X^323 + X^318 + X^317 +
    X^313 + X^312 + X^310 + X^309 + X^307 + X^306 + X^305 + X^302 + X^301 +
    X^298 + X^296 + X^294 + X^293 + X^292 + X^285 + X^278 + X^277 + X^276 +
    X^275 + X^272 + X^269 + X^266 + X^265 + X^264 + X^262 + X^261 + X^259 +
    X^258 + X^256 + X^253 + X^246 + X^245 + X^243 + X^242 + X^241 + X^238 +
    X^237 + X^234 + X^232 + X^229 + X^226 + X^225 + X^224 + X^222 + X^221 +
    X^220 + X^218 + X^216 + X^214 + X^213 + X^212 + X^208 + X^205 + X^198 +
    X^197 + X^196 + X^193 + X^192 + X^190 + X^189 + X^186 + X^182 + X^181 +
    X^179 + X^178 + X^177 + X^174 + X^173 + X^171 + X^170 + X^169 + X^168 +
    X^166 + X^165 + X^162 + X^161 + X^158 + X^157 + X^155 + X^154 + X^153 +
    X^152 + X^150 + X^149 + X^148 + X^145 + X^142 + X^141 + X^140 + X^133 +
    X^126 + X^125 + X^123 + X^120 + X^118 + X^117 + X^116 + X^113 + X^112 +
    X^109 + X^102 + X^101 + X^100 + X^98 + X^94 + X^93 + X^91 + X^90 +
    X^89 + X^86 + X^85 + X^83 + X^82 + X^81 + X^80 + X^78 + X^77 + X^76 +
    X^73 + X^72 + X^69 + X^62 + X^61 + X^60 + X^59 + X^54 + X^53 + X^52 +
    X^50 + X^48 + X^46 + X^45 + X^42 + X^40 + X^38 + X^37 + X^36 + X^35 +
    X^32 + X^29 + X^22 + X^21 + X^20 + X^17 + X^16 + X^14 + X^13 + X^10 +
    X^8 + X^6 + X^4 + X^2;
l:=47891146166194669675367248797495517594707810094989740173770621404397405\
      43970903739336135936970649474601608959493147659399495433873340533222\
      59124498269177310650885248209789392038650635;
K!P eq t^l;