Date:         Mon, 24 Oct 2005 08:34:14 -0400
Reply-To:     Antoine Joux 
Sender:       Number Theory List 
From:         Antoine Joux 
Subject:      Discrete logarithms in GF(65537^25) -- 120 digits -- 400 bits

Monday, October 24th, 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(65537^25). This was done in two days and a few hours
on a single Pentium mobile laptop at 1.6 Ghz. The approach is a new
variation on Adleman's function field sieve [Ad94], about which we are
currently preparing a paper [JoLe05]. 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 computation
was performed by Vercauteren and Lercier [LeVe05] using the approach
of torus representation introduced by Granger and Vercauteren in
[GrVe05].

With this new variation, we could not use our usual sieving code and
we wrote a new, independent sieving program. For the linear algebra,
we used our usual structured gaussian elimination and Lanczos
implementations.

Precisely, let

p=65537

GF(p^25) = GF(p)[t]/
  t^25 + 5*t^21 + 15*t^20 + 10*t^17 + 60*t^16 + 90*t^15 + 10*t^13 +
  90*t^12 + 270*t^11 + 270*t^10 + 5*t^9 + 60*t^8 + 270*t^7 + 540*t^6 +
  407*t^5 + 15*t^4 + 90*t^3 + 270*t^2 + 407*t + 247

and

  g = 3*t.

Let

 pi(t) = sum(i=0,24,(floor(Pi*p^(i+1))%p)*x^i)     # GP/PARI syntax
       = 41667*t^24 + 38062*t^23 + 60623*t^22 + 58559*t^21 +
       20236*t^20 + 47783*t^19 + 49050*t^18 + 37274*t^17 + 4366*t^16 +
       36803*t^15 + 18368*t^14 + 24622*t^13 + 9012*t^12 + 44161*t^11 +
       43372*t^10 + 20341*t^9 + 5644*t^8 + 46803*t^7 + 34689*t^6 +
       45877*t^5 + 9881*t^4 + 64918*t^3 + 32499*t^2 + 36552*t + 9279.


Then,

  pi(t)    =  g^405373694505244074458798850727154577337791051707463993575473\
     6348185260902857777282008537164926838353644893694741284146999.

Sieving:
--------

As usual, the sieving step found multiplicative relations between our
smoothness basis elements. The surprising fact is that this phase was
extremely fast and only took a couple of minutes to generate the
necessary equations.

Linear algebra:
---------------

The linear algebra was further divided in two phases.

We first applied structured Gaussian eliminations to reduce our system
to  79466 equations in 78465 unknowns with 3.8 millions non null entries.

Then, the bottleneck was the computation via Lanczos's algorithm.  Our
parallelized version of this algorithm took 2 days on the pentium
laptop.  At the end, we had logarithms modulo a large factor L of
p^25-1 for the elements of our smoothness basis.

Here, L=(p^25-1)/((p-1)*3571). To check these logarithms, we make use
of G=g^((p-1)*3571).

For instance,

    (t+1)^((p-1)*3571)=
    G^95805410880093234842298898214533393829434304594545362348\
      24840375483524017353229706334323184929723853320944439485
and

    (t^5+t+3)^((p-1)*3571)=
    G^46495712756925209185601240503381083970050573012881700517\
      18556686238431642289730613529631676496393555258546887691.


Individual Logarithms:
----------------------

We found in a few minutes two polynomials,

   num(t) = (t + 20471)*(t + 25396)*(t + 34766)*(t + 54898)*
            (t^2 + 29819*t + 6546)*(t^2 + 44017*t + 38392)*
            (t^2 + 54060*t + 4880)*(t^3 + 23811*t^2 + 6384*t + 3243)

and

   den(t) = (t + 18919)*(t + 31146)*(t + 38885)*(t + 53302)*
            (t^2 + 52365*t + 2605)*(t^3 + 29795*t^2 + 54653*t + 7616)*
            (12850*t^3 + 35335*t^2 + 14881*t + 36655)

such that

   pi(t) = num(t)/den(t) in GF(p^25).

Then, using special-q descents, we concluded the computation in a few
minutes of CPU-time.

So, as a conclusion, computing discrete logarithms in GF(65537^25)
using the function field sieve can be done very efficiently using a
total slightly above 2 days on a single laptop.


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