Dear all,
We are pleased to announce a new computation of a discrete logarithm modulo a
180 digit (596-bit) prime using the number field sieve algorithm. Previous
records are 130-digit (431-bit), 135-digit (448 bits) and 160-digit (530-bit)
primes (see [1], [2] and [3]).
We chose the following module:
p = RSA180 + 625942
= 191147927718986609689229466631454649812986246276667354864188503638\
807260703436799058776201365135161278134258296128109200046702912984\
568752800330221777752773957404540495707852046983
such that ell=(p-1)/2 is prime too. The element g=5 is a generator of the
multiplicative group mod p.
The "random" element for which we computed the logarithm is:
rsa1024 = 135066410865995223349603216278805969938881475605667027524485\
143851526510604859533833940287150571909441798207282164471551\
373680419703964191743046496589274256239341020864383202110372\
958725762358509643110564073501508187510676594629205563685529\
475213500852879416377328533906109750544334999811150056977236\
890927563
The result is:
logrsa1024 = 138670566126823584879625861326333326312363943825621039220\
215583346153783336272559955521970357301302912046310782908\
659450758549108092918331352215751346054755216673005939933\
186397777
Polynomial selection:
This step was performed using Kleinjung's algorithm. The computation took
around 2 core-months (2-GHz Intel E5-2650) and we have selected the two
following polynomials:
f(x) = 17153280*x^5 + 55645402596756*x^4 + 289642429100355466945*x^3
-5839034183672356481708253628*x^2 -3489195459822344127350367941464660*x
-24774668987371397084528618164507418928
g(x) = 633287365084897327346023*x - 25668325089522756076511361508720291
Sieving:
Relations were generated by lattice sieving. Algebraic and rational primes
below 800M were sieved and we allowed 2 large primes less than 2^29 on the
rational side and 3 large primes less than 2^30 on the algebraic side.
We sieved over special-q's between 80M and 380M. The sieving generated 253M
relations and took around 49.5 core-years (2-GHz Intel E5-2650)
Filtering:
In the 253M relations, there were 175M unique relations. The filtering step
produced a final matrix of 7.28M rows. The computation time is equivalent to 5
hours on one core (2-GHz Intel E5-2650).
Computing the Schirokauer maps took 0.9 core-year (2-GHz Intel E7540).
Linear algebra:
The linear algebra is modulo the 595-bit prime ell=(p-1)/2. The matrix contains
7.28M rows and columns with an average weight of 150 non-zero coefficients per
row. The matrix contains also 4 dense Schirokauer maps columns, whose elements
are modulo ell. We could consider only 3 Schirokauer maps columns.
The linear algebra was solved using the Block Wiedemann algorithm with the
blocking parameters m=24,n=12. The computation was run on a 768-core cluster
that contains 48 nodes connected with FDR Infiniband. Each node hosts two 2-GHZ
8-core Intel Xeon E5-2650 processors.
We have run 12 sequences in parallel, each running over 4 cores.
The scalar products and the evaluation phases required 38 days (around 80 core
years). The linear generator phase took 15 hours on 144 cores (around 0.25 core
year).
Once the linear algebra finished, we obtained the logarithms for many small
primes:
log2 = 143947424249804046894686521225835011553404529825698596989394995\
375091895197189866520496832751897255017764700065133297734751766\
543876760760613084110998852530852594071731064764347608
log3 = 125402553747091869459488367561520716928144625407579598051736139\
492527074873860357866906935921636923016180989364604005475590952\
635245779460745381246844568885972683224283333939126584
Individual logarithm:
It was calculated by special-q descent. Computing one individual logarithm
required a few hours.
Most of the code we used is freely available as part of the cado-nfs software
project (see [4]).
More details on the algorithms we used for the filtering and the linear algebra
are described in the papers [5] and [6].
Best regards,
Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel
Thomé.
[1] Antoine Joux and Reynald Lercier.
Discrete logarithms in GF(p) --- 130 digits.
E-mail to the NMBRTHRY mailing list;
http://listserv.nodak.edu/archives/nmbrthry.html, June 2005.
[2] Andrey Dorofeev, Denis Dygin and Dmitry Matyukhin.
Discrete logarithms in GF(p) --- 135 digits.
E-mail to the NMBRTHRY mailing list;
http://listserv.nodak.edu/archives/nmbrthry.html, December 2006.
[3] Thorsten Kleinjung.
Discrete logarithms in GF(p) --- 160 digits.
E-mail to the NMBRTHRY mailing list;
http://listserv.nodak.edu/archives/nmbrthry.html, February 2007.
[4] S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa, F. Morain,
E. Thomé and P. Zimmermann.
Cado-nfs: Crible algébrique: Distribution, optimisation - number field
sieve. http://cado-nfs.gforge.inria.fr/
[5] C. Bouvier.
The filtering step of discrete logarithm and integer factorization
algorithms.
Preprint, http://hal.inria.fr/hal-00734654, 2013.
[6] H. Jeljeli.
Resolution of Linear Algebra for the Discrete Logarithm Problem Using GPU
and Multi-core Architectures.
To appear in the proceedings of Euro-par 2014,
http://http://hal.inria.fr/hal-00946895, 2014.