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.
|