Date: Fri, 19 Jan 2001 14:38:16 -0500 Reply-To: lercier@mail.club-internet.fr Sender: Number Theory List From: Reynald Lercier Subject: Discrete logarithms in GF(p). Friday, January 19 2001. We are pleased to announce a new record for the general discrete logarithm problem. We were able to compute discrete logarithms modulo a 110 digits prime. This was done in three weeks on an unique 525MHz quadri-processors Digital Alpha Server 8400 computer. As far as we know, the largest such computation previously done was performed modulo a prime of 100 digits [JoLe00]. The software we used for this is a careful implementation of the algorithms described in [JoLe00]. In particular, our final computations of individual discrete logarithms took advantage, for the first time as far as we know, of an idea outlined by an anonymous referee of [JoLe00]. Precisely, let p = \lfloor 10^{109} \pi \rfloor+ 42842, = 3141592653589793238462643383279502884197169399375105820\ 9749445923078164062862089986280348253421170679821523707, g = 2, and y = \lfloor 10^{109} e \rfloor, = 2718281828459045235360287471352662497757247093699959574\ 9669676277240766303535475945713821785251664274274663919. Then y = g^2516201339165151955980892633211826668748782281651499701\ 3508788801824506959951249883413335095287799169652803855 and, similarly, y+1 = g^2953354352460702362920472394632606536248661667620359921\ 0749612536168255193406665021488238050013183047249625548. This result was obtained using an algebraic sieve as described from a theoretical point of view by Schirokauer [Schi93]. Here, it was done in three steps: _ the sieving step, _ the linear algebra, _ the final computation of individual logarithms. Sieving: -------- The sieving step consisted in finding couples (a,b) such that the principal ideal (a+bt) is of smooth norm in the so-called right'' number field defined by t^3-12*t^2-9*t+12 and such that (ac+bs) is of smooth norm in the so called left'' number field defined by s^2 -4489243468236265648432559009101212451*s -648807479839252024760428104033985336* 634438219795229554408337167341820523. Computationally speaking, this is done by working with 634438219795229554408337167341820523*s^2 -4489243468236265648432559009101212451*s -648807479839252024760428104033985336. An important fact about the degree 3 polynomial is that it's Galois group is of order 3. The corresponding number field has 2 fundamental units, 5*t^2+3*t-5 and 2*t^2-1, its class group is of order 3 and its index is equal to 2. Nothing is really known about the degree 2 polynomial, except of course, that the corresponding number field is a real quadratic field. The sieving was done efficiently following a now traditional sieving by vector'' with special-q'' technique. It yields many linear equations between logarithms of ideals'' of norms smaller than 8960470 (600000-th prime) in the left number field and of norms smaller than 2015180 (150000-th prime) in the right number field. After a 9 days computation on a quadri-processors alpha server 8400 computer, we obtained 1437324 equations with 767381 unknowns. Adding to these equations five Schirokauer maps (2 for the left number field and 3 for the right number field) took an additional day. Linear algebra: --------------- The linear algebra was further divided in two phases. We first applied structured Gaussian eliminations to reduce our system to 160329 equations in 160224 unknowns with 13547487 non null entries [LaOd91, JoLe00]. Time needed for this on only one processor was one day. Then, the critical phase was the final computation via Lanczos's algorithm [GoLo89]. Our parallelized version of this algorithm took 9 days over 4 processors. At the end, we had logarithms for ideals'' of small norms. As a consequence, we had logarithms for small primes. For instance, 3 = g^8746059669448118020838836498253062275923185542842052519\ 413367738090861096232704875362656162971943465436667588, 13 = g^1098101288586438303960796244800711416164536444076957947\ 2316191215698702193580318569311923257236716445637508030, 19 = g^5400028724818257576771001602268247602745624394453898649\ 45943757916343913895879442832053779977709005638683522, 23 = g^3953322621773495980046495989002353120467026863881559229\ 332231299838434286423825083299541292690613181958208454, etc ... Individual Logarithms: ---------------------- The last step consists in finding logarithm of y and y+1. A classical way to perform this is to find two smooth integers A and B of size \sqrt{p} such that y = A/B mod p. One drawback of this method is that we can only use primes which splits in an at least one factor base. As outlined in [JoLe00], we preferred here to take advantage of the Galois group of t^3-12*t^2-9*t+12. Precisely, we found in less than 6 hours, with a very crude implementation, two algebraic integers num = 1695632559598374872*t^2+1174482403645793433*t-3473011173155951179, den = 39725863324066699*t^2 + 369451304893599215*t + 1445172556352922562, such that 19*y = num/den modulo p and such that, in GP-PARI notation, the principal ideal (num) is equal to [[2, [1, 1, 1]~, 1, 1, [2, 1, 1]~] 3] * [[2, [3, 0, 1]~, 1, 1, [2, 2, 1]~] 1] * [[13, [-5, 1, 0]~, 1, 1, [-5, 5, 2]~] 1] * [[23, [8, 1, 0]~, 1, 1, [-10, 2, 2]~] 1] * [[37, [-7, 1, 0]~, 1, 1, [-7, -6, 2]~] 1] * [[37, [18, 1, 0]~, 1, 1, [13, 6, 2]~] 1] * [[842951, [-159601, 1, 0]~, 1, 1, [-43436, 159588, 2]~] 1] * [[359916165876481, [-125491257616506, 1, 0]~, 1, 1, \ [-129774599519000, 125491257616493, 2]~] 1] * [[594364606899841, [166256059556453, 1, 0]~, 1, 1, \ [-142021813670637, -166256059556466, 2]~] 1] * [[853787234948981, [345062301104299, 1, 0]~, 1, 1, \ [-135596430842632, -345062301104312, 2]~] 1], and the principal ideal (den) is equal to [[2, [1, 1, 1]~, 1, 1, [2, 1, 1]~] 1] * [[2, [2, 1, 0]~, 1, 1, [1, 1, 0]~] 1] * [[2, [3, 0, 1]~, 1, 1, [2, 2, 1]~] 3] * [[43, [18, 1, 0]~, 1, 1, [15, 12, 2]~] 1] * [[97, [6, 1, 0]~, 1, 1, [2, -19, 2]~] 1] * [[1069, [29, 1, 0]~, 1, 1, [111, -42, 2]~] 1] * [[2393, [283, 1, 0]~, 1, 1, [-279, -296, 2]~] 1] * [[4349, [73, 1, 0]~, 1, 1, [1847, -86, 2]~] 1] * [[11801, [-2531, 1, 0]~, 1, 1, [3040, 2518, 2]~] 1] * [[306347, [126036, 1, 0]~, 1, 1, [42993, -126049, 2]~] 1] * [[25465743776843, [6035268906098, 1, 0]~, 1, 1, \ [-9269111150513, -6035268906111, 2]~] 1] * [[160516256694037129, [16329411868846065, 1, 0]~, 1, 1, \ [-57833850813791900, -16329411868846078, 2]~] 1]. Then, using special-q techniques, computing discrete logarithms for the ideals'' of norms 359916165876481, 594364606899841, 853787234948981, 25465743776843, 160516256694037129 in the right number field was (thanks to one hour computation for each ideal, on a unique processor) equivalent to compute discrete logarithms for 18 ideals'' of norms larger than those of the factor basis in the left number field. Time needed for computing the 18 corresponding discrete logarithms was at most one hour for each on a unique processor. So, as a conclusion, we can say that time needed for computing discrete logarithms modulo a 110 digit prime on a 525 MHz quadri-processor alpha server 8400 computer is approximatively 12 hours for each, once the sieving step (10 days) and the linear algebra steps (10 days) is performed. Antoine JOUX (DCSSI, Issy les Moulineaux, Antoine.Joux@ens.fr), Reynald LERCIER (CELAR, Rennes, lercier@celar.fr). References: =========== [JoLe00] A. Joux and R. Lercier, Improvements to the general Number Field Sieve for discrete logarithms in prime fields, acceped for publication at Math. of Comp., 2000. Preprint 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. [LaOd91] 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.