Date: Wed, 9 Nov 2005 15:12:44 -0500
Reply-To: Antoine Joux
Sender: Number Theory List
From: Antoine Joux
Subject: Discrete logarithms in GF(370801^30) -- 168 digits -- 556 bits
Wednesday, November 9th, 2005.
We are pleased to announce a new record for the discrete logarithm
problem with medium sized base field. We were able to compute discrete
logarithms in GF(370801^30). This was done in less than 12 hours on a
1.15 GHz 16-processors HP AlphaServer GS1280. The approach is a our
variation on Adleman's function field sieve [Ad94], announced in
[JoLe05], about which we are currently preparing a paper. From a
complexity theoretic point of view, it gives a L(1/3) algorithm in its
range of applicability. As the regular function field sieve, it works
in three phases, sieving, linear algebra and individual logarithms.
As far as we know, the largest previous discrete logarithm
computations were performed, first by Vercauteren and Lercier [LeVe05]
(using the approach of torus representation introduced by Granger and
Vercauteren in [GrVe05]), then by Joux and Lercier [JoLe05] (using
this new variation of the function field sieve).
Precisely, let
p = 370801, GF(p^30) = GF(p)[t]/(t^30-17)
and
g = t - 6.
Let
pi(t) = sum(i=0,29,(floor(Pi*p^(i+1))%p)*x^i) # GP/PARI syntax
= 162147*t^29 + 338795*t^28 + 245060*t^27 + 323878*t^26 +
256820*t^25 + 63079*t^24 + 113985*t^23 + 210740*t^22 +
130675*t^21 + 97042*t^20 + 314407*t^19 + 352378*t^18 +
335134*t^17 + 342280*t^16 + 61106*t^15 + 272171*t^14 +
163784*t^13 + 240850*t^12 + 66741*t^11 + 265046*t^10 +
208274*t^9 + 275057*t^8 + 179507*t^7 + 229391*t^6 + 164345*t^5
+ 198249*t^4 + 3434*t^3 + 341005*t^2 + 258649*t + 52502.
Then,
pi(t) =
g^834934758318669039584738321669880646445961989720307919272366432\
574478787876554087500076043934132539884636443251840515509803922\
37533812685076653542562214928407573371226
Sieving:
--------
We define our algebraic function fields by f_1(X,t)=X-t^5 and
f_2(X,t)=X^6+X-17-t^5 and our smoothness basis contain places of
degree 1. We further use the fact that the reduction modulo p of these
places are conjugates each other by the Galois action given by
t->t^(p^6)=213181*t, we finally had to deal with only 148275 degree
one places. In this setting, our sieving software found 329082 useful
divisors of the form $Div X-(at+b)$ with $a$ and $b$ in $\GF{p}$, at
the cost of a 45 minutes computation.
Linear algebra:
---------------
We modified our implementation of the Lanczos algorithm to deal with
this case and we were finally able to solve a sparse system of 150270
equations in 148270 variables (11 entries by row equal to $p^{6i}$,
$i=0,\ldots 4$) at the cost of a 10 hours computation on 8 processors
of a 1.15 GHz HP AlphaServer GS1280. We worked modulo Q =
129717983265199170691 * 3780896193379818021601 *
27084969683231313608318791573698901.
To check these logarithms, we make use of G=g^((p^30-1)/Q).
For instance,
(t-1)^((p^30-1)/Q)=
G^858814752732049131584663651366411191299849888095646311187\
1919059262793471473
and
(t^5+t-1)^((p^30-1)/Q)=
G^540446525581805802972783150755982258918174413208848454470\
7050634558305662620
Individual Logarithms:
----------------------
We found in a few minutes two polynomials,
num(t) = (t + 55564) * (t + 128273) * (t + 320783) *
(t^2 + 67030 * t + 124516) * (t^2 + 141998 * t + 97806) *
(t^2 + 230077 * t + 272221) *
(t^3 + 281540 * t^2 + 359570 * t + 326930) *
(t^3 + 283548 * t^2 + 45715 * t + 97297)
and
den(t) = (t + 20273) * (t + 118843) * (t + 187495) *
(t + 223094) * (t + 334013) * (t^2 + 4164 * t + 141667) *
(t^2 + 16050 * t + 165737) * (t^2 + 343958 * t + 368575) *
(t^4 + 128873 * t^3 + 108876 * t^2 + 126230 * t + 114295)
such that
pi(t) = 33389 * num(t) / den(t) in GF(p^30).
Then, using special-q descents, we concluded the computation in 40
minutes of CPU-time.
So, as a conclusion, computing discrete logarithms in GF(370801^30)
using the function field sieve can be done very efficiently using a
total slightly less than 0.5 days on a 1.15 GHz HP AlphaServer
GS1280.
Antoine JOUX (DGA & Universite de Versailles, France,
antoine.joux(at)m4x.org),
Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org).
References:
===========
[Ad94] L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture
Notes in Math., 1994, volume 877.
[GrVe05] R. Granger and F. Vercauteren, ``On the discrete logarithm
problem on algebraic tori'', Crypto'05, LNCS 3621. pp 66--85
[JoLe05] A. Joux and R. Lercier, ``The function field sieve in the
medium prime case'', In preparation.
[LeVe05] R. Lercier and F. Vercauteren, ``Discrete logarithms in
GF(p^18) - 101 digits'', NMBRTHRY list, June 28th, 2005
[JoLe05] A. Joux and R. Lercier, ``Discrete logarithms in GF(65537^25)
-- 120 digits -- 400 bits'', NMBRTHRY list, October, 2005
|