Date: Sat, 18 Jun 2005 23:41:58 -0400 Reply-To: Antoine Joux Sender: Number Theory List From: Antoine Joux Subject: Discrete logarithms in GF(p) --- 130 digits Saturday, June 18th, 2005. The spectacular factorization of RSA-200 by Franke et al emphasizes the gap between factorization and discrete logarithms records and outlines that there is now room for improvement in computing discrete logarithms in finite fields, especially in prime fields. As a first attempt at filling this gap, we are very pleased to announce that we have computed discrete logarithms modulo a 130 digits prime. This was done in three weeks, on a unique 1.15 GHz 16-processors HP AlphaServer GS1280 computer. As far as we know, this is a new record for the general discrete logarithm problem. The approach followed here is close to our computation modulo a 120 digits prime in 2001 [JoLe01]. Except for the Structured Gaussian Elimination step which has been replaced by a novel and more efficient algorithm which might be of interest for other applications, this computation is mostly based on the algorithms described in [JoLe02]. * *** Precisely, we took a strong prime p = \lfloor 10^{129} \pi \rfloor + 38914, = 31415926535897932384626433832795028841971693993751058209749445923\ 07816406286208998628034825342117067982148086513282306647093883523 and a generator of the multiplicative group mod p g = 2 and a challenge number y = \lfloor 10^{129} e \rfloor, = 27182818284590452353602874713526624977572470936999595749669676277\ 24076630353547594571382178525166427427466391932003059921817413596. We computed that y = g^21138488223786795657590463012228607444377276414435077577308395472\ 0095258549520212875421011837642236137330107919426669776684829109 and, similarly, y+1 = g^44702322729716182227202277779696809350061507316078741399367293664\ 6278250727984316514493453566339150205697936921746933988890152955. * *** This result was obtained using a classical algebraic sieve as explained, from a theoretical viewpoint, by Schirokauer [Schi93]. So, it was done in three steps: _ the sieving step, _ the linear algebra, _ the final computation of individual logarithms. Lattice Sieving: ---------------- During the sieving step we found pairs (a,b) such that the principal ideal (a+bt) is of smooth norm in the so-called right'' number field defined by P(t) = t^3+12*t^2-13*t+3 and such that (ac+bs) is of smooth norm in the so called left'' number field defined by Q(s) = s^2 - 16909365834968487790611823369329079646668885*s + 20077251478186688202553272153633131115561222*c where c = 8258891862441565856565120580503979696050188. Taken together, these two polynomials are related to p, by the fact that P(X) and Q(c*X) have a common root modulo p. The Galois group of the degree three polynomial is of order three. The unit group of the corresponding number field can be defined by two fundamental units, 9*t^2+117*t-41 and 3*t-1. The class group is of order one and all ideals are principal in this number field. Much less is known about the degree two polynomial except that the corresponding number field is an imaginary quadratic field. The sieving was done efficiently following a traditional sieving by vector'' with special-q'' technique. It yields many linear equations between logarithms of ideals'' of norms smaller than 18815207 (1200000-th prime ideal) in the left number field and of norms smaller than 5799977 (400000-th prime ideal) in the right number field. After a 13 days computation, we obtained 1946916 useful equations with 1466090 unknowns. At this point, it usually remains to add Schirokauer maps to these equations. In our computation, we added none. We prefered for the right number field, instead of what was done in [JoLe01], to add explicitly the fundamental units contribution taking advantage that any ideal on the right number field is principal. Moreover, no map are needed for the imaginary quadratic number field since the unit group is trivial. We just added a renormalization unknown (the same for all equations) to account for the constant c in Q(s). Adding the units contribution took 2 hours. Linear algebra: --------------- The linear algebra was further divided in two phases. We first applied structured Gaussian eliminations to reduce our system to 433181 equations and 432172 unknowns with 35323996 non zero entries. Thanks to a novel algorithm, time needed for this was less than 15 minutes on a single processor. Then, the critical phase was the final computation via Lanczos's algorithm. Our parallelized version of this algorithm took 8 days. At the end, we had logarithms for ideals'' of small norms. As a consequence, we had logarithms for the corresponding small primes. For instance, 3 = g^18935022642385712265442162784856643707918464682969857705736136901\ 41150005617588988077853204617146221819982684416360486509655807744 11 = g^4237102728490621953875844147019736370886375829289178182680995735\ 01636485194195766410542501760951486387180557151162653894308532555 37 = g^9506461927181030030008386959918266024894356371823647783744271773\ 64890693263742686571949298174887812261560755967507029212728831603 and so on ... Individual Logarithms: ---------------------- We take advantage of the Galois group of t^3+12*t^2-13*t+3 as in [JoLe02]. Let r be the common root modulo p of P(X) and Q(c*X). r = 9043915310378454904190271386750659804308441369321835953747752084\ 65350069017567424420782222065306959877189077428581266221096718153 We found in a few hours, using a very crude implementation, two algebraic numbers, num = 3067768196913421887864*r^2 + 3564986601609873727783*r + 11102447291325953922104 and den = -1886510641162700085744*r^2 - 614947335528224906300*r + 1174119585425048306413 such that g^2*y = -num/den modulo p, and satisfying the following algebraic relations, num = -(-1+r) * (-r^2-11*r+4) * (r^2+7*r-1) * (38*r^2-5*r-14) * (-58*r^2+51*r-10) * (-19968234615452*r^2-253095266814753*r+88773815898184) * (-103527432682334747*r^2-1277679011473992359*r+909588468749207990) * (52211650*r^2+648088367*r-410299369) * (-10551006859*r^2-133733301857*r+46901909959) * (9*r^2+117*r-41)^(-12) * (3*r-1)^37 and den = (-1+2*r)^2 * (-250393155*r^2-3090199419*r+2200155182) * (-17257853*r^2-218912874*r+74493007) * (-6714524974*r^2-85147186243*r+29313654043) * (-110524082322*r^2-1346736343362*r+1196134561937) * (-1643288515585*r^2-20830007491278*r+7286141994812) * (9*r^2+117*r-41)^(-17) * (3*r-1)^49 These equalities come from the factorization in the right number field of smooth algebraic integers obtained once substituted r by t in num and den. Each factor is then the generator of a prime ideal with a much smaller norm. Then, using special-q descents, computing discrete logarithms for the ideals'' of norm 2592589, 17109767, 88447559, 18475577467, 108621101466083, 3525111154062353, 140633755138925249, 59677745837274488381 and 1019544752700081075653 in the right number field was (thanks to a few minutes computation for each ideal, on a unique processor) equivalent to compute discrete logarithms for ideals'' of norms larger than those of the factor basis in the left number field. After numerous iterations, we were able to compute num = g^13662163601403810017674251686005246963595557866172606992339095483\ 08183912002005416888157658497005919998119321431364412826732967004 and den = g^27256278046974096644228422301179900640143677221604628339482978897\ 41996856595589703326754059330422217851863256768578896373595079654. Finally, this yielded the discrete logarithm of y. * *** So, as a conclusion, the time for computing a discrete logarithms modulo a 130-digit prime on a 1.15 GHz 16-processors HP AlphaServer GS1280 computer with our current implementation is a few hours, once the sieving step (13 days) and the linear algebra steps (8 days) have both been performed. Antoine JOUX (DGA and Universite de Versailles, France, antoine.joux(at)m4x.org), Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org). References: =========== [JoLe02] A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. Math. Comp., 72(242):953-967, 2002. [JoLe01] A. Joux and R. Lercier, Discrete logarithms in GF(p)'', Tuesday, April 17 2001. NMBRTHRY Mailing List. Available at http://www.medicis.polytechnique.fr/~lercier. [Schi93] O. Schirokauer, Discrete Logarithms and local units. Phil. Trans. R. Soc Lond. A 345, pages 409-423, 1993.