Date:         Sat, 23 Feb 2002 21:04:06 -0500
Reply-To:     Emmanuel Thomé <[log in to unmask]>
Sender:       Number Theory List <[log in to unmask]>
From:         Emmanuel Thomé <[log in to unmask]>
Subject:      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\'erard 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\"el 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.
         4f3K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3W2A6i4K6u0W2N6h3W2T1i4K6u0W2L8X3!0Q4x3V1k6Q4y4@1g2D9j5i4u0K6M7W2)9J5c8X3y4J5j5i4m8@1L8$3I4G2k6%4W2Q4x3V1k6U0M7Y4j5I4L8U0m8Q4x3X3b7I4i4K6u0W2K9s2c8E0L8l9`.`.
[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
         f0cK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3I4A6M7%4c8K6k6i4u0$3i4K6u0W2L8X3!0V1j5h3E0Q4x3X3g2W2k6s2g2Q4x3V1k6S2M7X3y4Z5K9i4k6W2M7#2)9J5c8X3&6E0j5Y4u0@1K9s2u0&6i4K6u0W2K9s2c8E0L8l9`.`.
[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\'e, 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\'e, 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: 02dK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3I4A6P5q4)9J5k6i4m8G2L8s2W2@1k6h3y4Z5L8X3W2I4N6h3g2Q4x3X3g2X3M7W2)9J5c8V1I4S2j5X3!0Q4x3V1k6q4L8h3#2S2L8Y4g2W2L8q4)9J5k6g2c8Z5L8$3#2W2i4K6u0r3

------ 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:=478911461661946696753672487974955175947078100949897401737706214043974\
054397090373933613593697064947460160895949314765939949543387334053322259\
124498269177310650885248209789392038650635;

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;

Source from http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0202&L=nmbrthry&F=&S=&P=2568

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课