Date:         Tue, 26 May 1998 14:35:40 -0400
Reply-To:     Reynald Lercier <lercier@hol.fr>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald Lercier <lercier@hol.fr>
Subject:      Discrete logarithms in GF(p).

CELAR, Rennes (France), Tuesday May 26 1998.

We are pleased to announce a new record for the general discrete
logarithm problem. We were able to compute discrete logarithms
modulo a 90 digits prime on a network of Pentium PRO 180 MHz based
PC. As far as we know, the largest such computation done previously
was performed modulo a prime of 85 digits and is due to D. Weber
[DeWeZa96].

Precisely, let
  p = \lfloor 10^{89} \pi \rfloor+ 156137,
    = 3141592653589793238462643383279502884197169399\
      37510582097494459230781640628620899862959619,
  g = 2,
and
  y = \lfloor 10^{89} e \rfloor,
    = 27182818284590452353602874713526624977572470936\
      9995957496696762772407663035354759457138217.

Then
  y = g^176713807211421696273204823407162027230205795\
        2449914157493844716677918658538374188101093,
  y+1 = g^3116041987058269748820788091978682382044912\
          0001421617617058468654271221802926927230033421,
  y+2 = g^3089883293350445253338277649145014072371680\
          34577534227927033783999866774252739278678837301,
  y+3 = g^6580688800278838010371298688366325318718350\
          5405451188935055113209887949364255134815297846,
and
  y+4 = g^4069601088212869919975316593460491889486849\
          0454360617887844587935353795462185105078977093.

This result was obtained using the quadratic sieve as described by
Lamacchia and Odlyzko [LaOd91]. It was classically done in three steps:
  _ the sieving step,
  _ the linear algebra,
  _ the final computation of individual logarithms.

The sieving step yields many linear equations between logarithms of
small primes (smaller than 1299710) or ideals in Q(\sqrt(-2)) of small
norms (smaller than 350378). Of course, we authorize equations with
large primes on each side. Such equations are usually called FF
(Full-Full), FP (Full-Partial), PF (Partial-Full) or PP
(Partial-Partial). After a total cpu time of 4 months, we precisely
obtained:

------------------------------------------------------------------
          |    FF    |    FP    |    PF    |    PP    |  Total   |
------------------------------------------------------------------
equations |    83519 |   235921 |  1377187 |  4966470 |  6663097 |
------------------------------------------------------------------

The linear algebra was further divided in three phases:
  _ In a first phase, we remove in few hours (mostly to
uncompress/compress data on disk) all the useless equations involving
variables not seen anywhere else. This phase was applied repeatedly
until no more equations where useless. In our case, 976062 equations
in 674564 unknowns remained after this.
  _ We then applied structured Gaussian eliminations to reduce our
system to 61136 equations in 61036 unknowns with 5683954 non null
entries [LaOd91a]. Time needed for this was less than one day.
  _ Another critical phase is the final computation via Lanczos's
algorithm [GoLo89]. It took three weeks. At the end, we had logarithms
for small primes, for instance,
  3 = g^19748300961167147793248409109777288916563744188\
        3405533161063698387711654453959032453019844,
  5 = g^14911991564240187116623990082296104898497606799\
        3569475849547058535625211933991916749097892,
  7 = g^20534713616438695604297290160284536202786764235\
        9069620025634227501709422532443486030114180
  ...

The last step consists in finding logarithms of integers x. A
classical way to perform this is to find two smooth integers A and B
of size \sqrt{p} such that x = A/B mod p. For instance, let
  A = 7*167*347*421*1049*3067*3079*3319*174077*293263*38174761*82044163,
and
  B = 5^2*17*1187*1877*2039*3019*110863*207589*2903639*5397737*1064068253,
then
 1299709^92 y  = A/B mod p.

Antoine JOUX (ajoux@celar.fr),
Reynald LERCIER (lercier@hol.fr).

References:

[DeWeZa96] T.F. Denny, D. Weber and J. Zayer, Discrete logarithm mod p,
           Email on the Number Theory Mailing List, Universitaet des
           Saarlandes, november 1996.

[LaOd91] B.A. Lamacchia and A.M. Odlyzko, Solving large sparse linear
         systems over finite fields, A.J. Menezes and S.A. Vanstone
         editors, volume 537, Lecture Notes In Computer Science,
         Springer-Verlag, pages 109-133, Advances in Cryptology,
         CRYPTO '90, 1990.


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