Date: Tue, 28 Jun 2005 19:37:11 -0400
Reply-To: Frederik Vercauteren
Sender: Number Theory List
From: Frederik Vercauteren
Subject: Discrete logarithms in GF(p^18) - 101 digits
We are pleased to announce the computation of discrete logarithms in
GF(p^18) with p = 370801, so p^18 has 101 digits. The computation took a
bit less than one week on 10 AMD's Athlon(TM) XP 2000+. As far a we know
this is a new record for the discrete logarithm problem in GF(p^n) where
neither p nor n is extremely small. Detailed information (including the
DLOGs for all factor base elements) can be found at
http://www.esat.kuleuven.ac.be/~fvercaut/dlog/
The remainder of this email gives a summary.
-------------------------------------------------------------------------
The computation of discrete logarithms (DLOGs) in a finite field GF(p^n)
is a fairly well studied problem, and different algorithms exist depending
on the ratio of n and p. For large p and small n, an adaptation of the
general number field sieve should be used (see [JoLe02a]), whereas for
small p and large n, the function field sieve (including Coppersmith's
algorithm) (see [JoLe02b]) is most appropriate. For the other cases
there is currently only the algorithm due to Adleman and DeMarrais
[AdDe93].
From an implementation point of view, there has been quite a lot of effort
dealing with the extreme cases, i.e.
- GF(p): the current record is the computation of DLOGs modulo a 130-digit
prime by Joux and Lercier [JoLe05].
- GF(2^n): the current record is the computation of DLOGs in GF(2^n) with
n = 607 by Thom\'e [Th01]
So far there have been no large computations in any other fields GF(p^n)
where neither p, nor n is extremely small.
As shown by Lenstra [Len97], the hardness of the discrete logarithm
problem (DLP) in GF(p^n) is mainly determined by the DLP in the subgroup
of GF(p^n)^x of order Phi_n(p) with Phi_n(x) the n-th cyclotomic
polynomial. Furthermore, it is well known that this subgroup is
isomorphic to the GF(p)-rational points on the algebraic torus T_n
[RuSi03].
Recently, Granger and Vercauteren [GrVer05] combined an idea to Gaudry
[Ga04] with rational parametrisations of algebraic tori that resulted in a
new algorithm to compute DLOGs in GF(p^n) where n is divisible by 6. This
algorithm is an index calculus type algorithm and thus consists of three
steps:
- relation collection
- linear algebra
- individual logarithms
Relation collection:
====================
The relations were generated by Vercauteren using a simple Magma program
that implements the algorithm described in [GrVer05]. Since this process
is trivially parallelizable, the relation collection phase was distributed
over 10 AMD's Athlon(TM) XP 2000+ running Debian Linux 2.4.22. After
slightly less than one week of computation, we obtained 411719 relations.
The total CPU time spent on the relation collection is about 600 MIPSY.
Note that the sieving step of the GNFS to compute DLOGs in GF(p) with p a
100-digit prime as reported by Joux and Lercier [JoLe02a] took about 300
MIPSY.
Linear algebra:
===============
The linear algebra problem was solved by Lercier on a unique 1.15 GHz
16-processor HP AlphaServer GS1280 computer.
In order to find the fastest way to solve this type of problem, we
considered three matrices:
- the matrix without SGE, that is 385005 x 370004 with 2310030 entries
- the matrix after a normal SGE, that is 183619 x 182618 with 3862117
entries
- the matrix after a heavy SGE, that is 128684 x 127683 with 17760811
entries
Then the time needed with 1, 2, 4, 8 or 16 processors was measured.
Timings (hours) on 1.15 GHz 16-processors HP AlphaServer GS1280 computer
SGE & 1 proc & 2 proc & 4 proc & 8 proc & 16 proc
none & 166h & 140h & 84h & 41h & 30h
normal & 56h & 45h & 24h & 13h & 11h
heavy & 75h & 60h & 30h & 15h & 12h
The speedup obtained after increasing the number of processors is not very
good. This is mainly because the matrix is very sparse and the modulus is
also rather small. Therefore the amount of communication is quite high.
Individual discrete logarithms:
===============================
Our experiments show that the probability of obtaining a relation is in
fact somewhat higher than the expected 1/720, namely 1/710. The time
taken for one decomposition trial was about 198 ms. Therefore, the total
average time to compute the DLOG of a random element of T_18(GF(p)) is
only 14 seconds, which is very fast compared to the timings obtained by
GNFS.
So, as a conclusion, the time for computing discrete logarithms in
GF(p^18) with p = 370801, is a mere 14 seconds once the relation
collection phase (7 days on 10 AMD's Athlon(TM) XP 2000+) and the linear
algebra step (0.5 days on a 1.15 GHz 16-processors HP AlphaServer GS1280)
have been performed.
Frederik VERCAUTEREN (COSIC, K.U.Leuven, Belgium)
Reynald LERCIER (CELAR, Rennes, France)
=========================================================================
[AdDe93] L. M. Adleman and J. DeMarrais, A subexponential algorithm for
discrete logarithms over all finite fields. Math. Comp., 61(203):1-15,
1993.
[Ga04] P. Gaudry. Index calculus for abelian varieties and the elliptic
curve discrete logarithm problem. Cryptology ePrint Archive, Report
2004/073.
[GrVer05] R. Granger and F. Vercauteren. On the Discrete Logarithm Problem
on Algebraic Tori. In Advances in Cryptology - CRYPTO 2005, Lecture Notes
in Computer Science Springer, 2005.
[JoLe02a] 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.
[JoLe02b] A. Joux et R. Lercier, The function field sieve is quite
special. In D.R. Kohel C. Fieker, editor, Algorithmic number theory V,
Lecture Notes in Computer Science Springer, 2002.
[JoLe01] A. Joux and R. Lercier, Discrete logarithms in GF(p) --- 130
digits, 18 June 2005. Email to NMBRTHRY Mailing List.
[Len97] A. K. Lenstra. Using cyclotomic polynomials to construct efficient
discrete logarithm cryptosystems over finite fields. In Proceedings of
ACISP97, Lecture Notes in Computer Science Springer, 1997.
[RuSi03] K. Rubin and A. Silverberg. Torus-based cryptography. In Advances
in Cryptology - CRYPTO 2003, Lecture Notes in Computer Science Springer,
2005.
[Th01] E. Thom\'e, Computation of Discrete Logarithms in _F^2607. In C.
Boyd, Advances in Cryptology - ASIACRYPT 2001, Lecture Notes in Computer
Science, 2001.
|