Date: Tue, 26 May 1998 14:35:40 -0400 Reply-To: Reynald Lercier Sender: Number Theory List From: Reynald Lercier 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.