Dear Number Theorists,
We are pleased to announce a new computation of a discrete logarithm in a
finite field whose order has 160 digits and is a degree 2 extension of a
prime field. The algorithm used was the number field sieve (NFS), with
various modifications. The total computing time was equivalent to 68 days
on one core of CPU (sieving) and 30 hours on a GPU (linear algebra).
To our knowledge, this kind of computation has not be reported before,
but for reference, we recall that until the recent announcement of 180
digits, the record for discrete log computation in a prime field was
also of 160 digits.
The 80-digit prime p was chosen from the decimal digits of pi, such that both
p-1 and p+1 have a large prime factor. We also forced p to be 7 modulo 8,
so that we could use our favorite cyclotomic polynomial (see below), but
other congruences modulo 8 can be tackled in about the same running time.
p = 3141592653589793238462643383279502884197\
1693993751058209749445923078164063079607
Computing logarithms modulo p-1 raises no particular difficulty, and we
concentrated on the logarithms modulo the following prime divisor of p+1:
ell = 3926990816987241548078304229099378605246\
461749218882276218680740384770507884951
The defining polynomial of GF(p^2) over GF(p) was chosen to be:
phi = t^2 + 8827843659566562900817004173601064660843\
646662444652921581289174137495040966990*t + 1
and we used g = t + 2 as a generator.
The logarithm in base g of the following "random" element:
s = Floor(Pi*(2^264)/4)*t + Floor(EulerGamma*2^264)
is then
log(s) = 4317246464747174995321414320990695178326\
07980262114471597315861099398586114668 modulo ell.
Verification scripts are provided at the end of the message.
Details on the computation:
===========================
Most of the computation uses software that is freely available:
- CADO-NFS [1] for the sieving, filtering, and most of the individual
logarithms;
- Jeljeli's GPU linear algebra package [2].
Polynomial selection:
---------------------
For this step, we used a new technique that provides smaller sizes than
the method by Joux, Lercier, Smart and Vercauteren [3]. Moreover the two
polynomials are chosen with nice properties so that speed-up are possible
at different stages. This computation takes essentially no time. We used
f = x^4 + 1
g = 22253888644283440595423136557267278406930*x^2
+ 41388856349384521065766679356490536297931*x
+ 22253888644283440595423136557267278406930.
Note that both polynomials are reciprocal, and that g has negative
discriminant.
Relation collection:
--------------------
We used the lattice sieving software of CADO-NFS for this step. Prime
ideals on both sides that are below 40M were sieved and we allowed 2
large primes less than 2^27 on each side. We sieved over special-q's on
the g-side between 40M and 60M. The sieving generated 15M relations and
took around 68 core-days (2-GHz Intel E5-2650).
Due to the reciprocal polynomials, we sieved only half of the special-q
in the target range.
Filtering:
----------
The filtering step was run as usual, but we modified it to take into
account the Galois action on the ideals: we selected a representative
ideal in each orbit under the action $x \mapsto x^{-1}$, and rewrote all
the relations in terms of these representatives only. The output of the
filtering step was a matrix with 839,244 rows and columns, having on
average 83.6 non-zero entries per row.
Due to number field properties, it was not necessary to add columns with
Schirokauer maps.
Linear algebra:
---------------
We used Jeljeli's implementation of Block Wiedemann's algorithm for GPUs.
In fact, this was a small enough computation so that we did not
distribute it on several cards: we used a non-blocked version.
The total running time for this step was around 30.3 hours on an NVidia
GTX 680 graphic card.
At the end of the linear algebra we know the virtual logarithms of almost
all prime ideals of degree one above primes of at most 26 bits, and of
some of those above primes of 27 bits. At this point we could test that
the logs on the f-side were correct.
Individual logarithm stage:
---------------------------
We started by looking for an integer e such that z = s^e, seen as an
element of the number field of f, is smooth. After a few core-hours, we
found a value of e such that z = z1/z2 with z1 and z2 splitting completely
into prime ideals of at most 60 bits. With the lattice-sieving software
of CADO-NFS, we then performed a "special-q descent" for each of these
prime ideals. We remark that one of the prime ideals in z1 was an ideal
of degree 2 above 43, that had to be descended in a specific way,
starting with a polynomial of degree 2 instead of 1. The total time for
descending all the prime ideals was a few minutes.
Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain
References:
===========
[1] S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa,
F. Morain, E. Thomé and P. Zimmermann.
CADO-NFS. http://cado-nfs.gforge.inria.fr/
[2] H. Jeljeli.
An implementation of the Block-Wiedemann algorithm on NVIDIA-GPUs
using the Residue Number System (RNS) arithmetic.
Available from http://www.loria.fr/~hjeljeli/
[3] A. Joux, R. Lercier, N. Smart, F. Vercauteren.
The number field sieve in the medium prime case.
CRYPTO 2006, LNCS 4117, p. 326-344, Springer.
Verification scripts:
=====================
Magma script:
-------------
p := 31415926535897932384626433832795028841971693993751058209749445923078164063079607;
ell := 3926990816987241548078304229099378605246461749218882276218680740384770507884951;
h := (p^2-1) div ell;
varphi:=Polynomial([GF(p) | 1,8827843659566562900817004173601064660843646662444652921581289174137495040966990,1]);
Fpn:=ext;
gen := t + 2;
R:=RealField(280);
s1:=Floor(Pi(R)*2^264/4);
s0:=Floor(EulerGamma(R)*2^264);
target:=s1*t + s0;
log_target := 431724646474717499532141432099069517832607980262114471597315861099398586114668;
assert target^h eq gen^(h*log_target);
Sage script:
------------
p = 31415926535897932384626433832795028841971693993751058209749445923078164063079607
ell = 3926990816987241548078304229099378605246461749218882276218680740384770507884951
h = (p^2-1) // ell
varphi=GF(p)['x'] ([
1,8827843659566562900817004173601064660843646662444652921581289174137495040966990,1])
Fpn.=GF(p^2,modulus=varphi);
gen = t + 2
target = 23281380921073044753935036337774711209817176149017115517361417671548089245835857*t + 17110273991540504259863674318281574234623888530768743939507283540597018487405966
log_target = 431724646474717499532141432099069517832607980262114471597315861099398586114668
assert target^h == gen^(h*log_target)