Date: Fri, 19 Jan 2001 14:38:16 -0500
Reply-To: lercier@mail.club-internet.fr
Sender: Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From: Reynald Lercier <lercier@mail.club-internet.fr>
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.
|