New Discrete Log Record due to Joux and Lercier
dmolnar
dmolnar at hcs.harvard.edu
Wed Apr 18 01:09:38 EDT 2001
>From the NMBRTHRY at LISTSERV.NODAK.EDU mailing list:
Date: Tue, 17 Apr 2001 22:52:56 -0400
From: Reynald LERCIER <lercier at mail.club-internet.fr>
Subject: Discrete logarithms in GF(p)
Tuesday, April 17 2001.
We are very pleased to announce a new record for the general discrete
logarithm problem. We were able to compute discrete logarithms modulo
a 120 digits prime. This was done in 10 weeks, on a unique 525MHz
quadri-processors Digital Alpha Server 8400 computer.
The approach we followed for this computation is close to the approach
we used for computing discrete logarithms modulo a 110 digits prime
[JoLe01]. It is mostly based on algorithms described in [JoLe00].
Precisely, let
p = \lfloor 10^{119} \pi \rfloor+ 207819,
= 314159265358979323846264338327950288419716939937510582097494\
459230781640628620899862803482534211706798214808651328438483,
g = 2,
and
y = \lfloor 10^{119} e \rfloor,
= 271828182845904523536028747135266249775724709369995957496696\
762772407663035354759457138217852516642742746639193200305992.
Then
y = g^262112280685811387636008622038191827370390768520656974243035\
380382193478767436018681449804940840373741641452864730765082,
and, similarly,
y+1 = g^39657965519539238631090956325038481900751981791165229696297\
421520645832904710912189562251329527994908449750607046857937.
This result was obtained using a now classical algebraic sieve as
explained, from a theoretical point of view, by Schirokauer
[Schi93]. So, 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-9*t^2-9*t+9
and such that (ac+bs) is of smooth norm in the so called ``left''
number field defined by
s^2
-7374389167922711279538633461199308033087*s
-333238556260219119547406855509826713348*c
where
c = 1201639291188427271122019272295979872125.
The Galois group of the degree 3 polynomial is of order 3. The
corresponding number field has 2 fundamental units, 1/12*t^2-t+1/4 and
-1/12*t^2+1/2*t+5/4, its class group is of order 1 and its index is
equal to 2^6*3^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
15485870 (1000000-th prime) in the left number field and of norms
smaller than 3497870 (250000-th prime) in the right number field.
After a 40 days computation on a quadri-processors alpha server 8400
computer, we obtained 2685597 equations with 1242551 unknowns.
At this point, it usually remains to add 5 Schirokauer maps to these
equations. Here, we added only 2 maps (for the left number field) and
prefer for the right number field, instead of what was done in
[JoLe01], to add explicitly fundamental units contribution taking
advantage that any ideal on the right number field is principal.
This step (maps+units) took one day.
Linear algebra:
---------------
The linear algebra was further divided in two phases.
We first applied structured Gaussian eliminations to reduce our system
to 271654 equations in 271552 unknowns with 22690782 non null entries
[LaOd91, JoLe00]. Time needed for this on only one processor was less
than 1 day.
Then, the critical phase was the final computation via Lanczos's
algorithm [GoLo89]. Our parallelized version of this algorithm took 30
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 ^ 28812588093314776509699010256332271205911219293533606948309\
244629961378102894412283315317373685769257402738003506902138,
5 = g ^ 21755718305811583829459340786707488931552080300620288049491\
6079418842612898727245046247623746814003335266081854116641401,
7 = g ^ 30620343436458977106289725314901617172209074240481960209355\
5007057950445875245076830599652008193628520847056151254242513,
11 = g ^ 26369065546060570062275123759054389628546695463387446804852\
2904503050215021182824543943461120732653168766053846377967922,
etc ...
Individual Logarithms:
----------------------
We take advantage of the Galois group of t^3-12*t^2-9*t+12 [JoLe00].
Precisely, we found in less than 6 hours, using our very crude
implementation, two algebraic integers
num = 136919628471533453465*t^2
- 109185518772042207040*t
- 218010383119442982304
and
den = 90752177247861263294*t^2
+ 5976502381138861785*t
+ 161979899979266169279
such that
19^2*y = num/den modulo p
and such that,
in GP-PARI notation, the principal ideal (num) is equal to
[[53, [7, 2, 0]~, 1, 1, [-18, 19, 12]~] 1] *
[[431, [-20, 2, 0]~, 1, 1, [168, 20, 12]~] 1] *
[[2179, [140, 2, 0]~, 1, 1, [-502, -300, 12]~] 1] *
[[16831, [-3928, 2, 0]~, 1, 1, [-1478, 7836, 12]~] 1] *
[[156781, [-45467, 2, 0]~, 1, 1, [15351, -65867, 12]~] 1] *
[[7691507, [-3118090, 2, 0]~, 1, 1,
[-1592322, -1455347, 12]~] 1] *
[[5847120361, [-944554227, 2, 0]~, 1, 1,
[-2613536996, 1889108434, 12]~] 1] *
[[7689099923, [-1979641955, 2, 0]~, 1, 1,
[-1763503409, -3729816033, 12]~] 1] *
[[14023824873312563677, [2910448673841826685, 2, 0]~, 1, 1,
[-4872413772263364932, -5820897347683653390, 12]~] 1]
and the principal ideal (den) is equal to
[[2, [2, 0, 0]~, 1, 3, [1, 0, 0]~] 1] *
[[3, [1, -1, 1]~, 3, 1, [2, 2, 0]~] 3] *
[[19, [8, 2, 0]~, 1, 1, [-3, 2, -7]~] 1] *
[[1873, [-237, 2, 0]~, 1, 1, [889, 454, 12]~] 1] *
[[110359, [36889, 2, 0]~, 1, 1, [-37268, 36561, 12]~] 1] *
[[2672473789, [-932319595, 2, 0]~, 1, 1,
[1125968488, -807834619, 12]~] 1] *
[[626844366559, [-255501920253, 2, 0]~, 1, 1,
[-211702090482, -115840526073, 12]~] 1] *
[[685495972547, [-197652881054, 2, 0]~, 1, 1,
[-276404069769, -290190210459, 12]~] 1] *
[[641614040507139551, [33835176915624305, 2, 0]~, 1, 1,
[159262188369356649, -67670353831248630, 12]~] 1]
Then, using special-q descents, computing discrete ``logarithms for
the ideals'' of norms 7691507, 5847120361, 7689099923,
14023824873312563677 and 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
ideals'' of norms larger than those of the factor basis in the
left number field. Time needed for computing the 31 corresponding
discrete logarithms was at most one hour for each on a unique
processor.
So, as a conclusion, time that we need for computing discrete
logarithms modulo a 120 digit prime on a 525 MHz quadri-processor
alpha server 8400 computer is approximatively 12 hours for each, once
the sieving step (42 days) and the linear algebra steps (30 days) is
performed.
Antoine JOUX (DCSSI, Issy les Moulineaux, France, Antoine.Joux at ens.fr),
Reynald LERCIER (CELAR, Rennes, France, lercier at celar.fr).
References:
===========
[JoLe01] A. Joux and R. Lercier, ``Discrete logarithms in GF(p)'',
January 19 2001. Announce on the NMBRTHRY Mailing List.
Available at http://www.medicis.polytechnique.fr/~lercier.
[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.
------------------------------
End of NMBRTHRY Digest - 16 Apr 2001 to 17 Apr 2001 (#2001-56)
**************************************************************
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography
mailing list