Discrete logarithm records
Encyclopedia
Discrete logarithm records are the best results achieved to date in solving the discrete logarithm
problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G. The difficulty of this problem is the basis for the security of several cryptographic systems, including Diffie–Hellman key agreement, ElGamal encryption
, the ElGamal signature scheme
, the Digital Signature Algorithm
, and the elliptic curve cryptography
analogs of these. Common choices for G used in these algorithms include the multiplicative group of integers modulo p, the multiplicative group of a finite field
, and the group of points on an elliptic curve
modulo p or over a finite field
.
in three weeks, using a 1.15 GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.
On 5 Feb 2007 this was superseded by the announcement by Thorsten Kleinjung of the computation of a discrete logarithm modulo a 160-digit (530-bit) safe prime
, again using the number field sieve. Most of the computation was done using idle time on various PCs and on a parallel computing cluster.
to compute a discrete logarithm in a field of 2613 elements. The computation took 17 days on four 16-processor (1.3 GHz) nodes of the Itanium 2-based Bull computer Teranova.
The current record (as of 2010) for a field of characteristic 3 was announced by Takuya Hayashi et al., who computed a discrete logarithm in the field of 36 · 71 elements, using a variation on the function field sieve
.
This also holds the record for the computation over the largest field (676 bits) of any type.
Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 6553725 elements (401 bits) announced on 24 Oct 2005, and in a field of 37080130 elements (556 bits) announced on 9 Nov 2005.
The Level I challenges which have been met are:
None of the 131-bit (or larger) challenges have been met as of 2010.
In July 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery announced that they had carried out a discrete logarithm computation on an elliptic curve modulo a 112-bit prime. The computation was done on a cluster of over 200 PlayStation 3 game consoles over about 6 months. They used the common parallelized version of Pollard rho method
.
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G. The difficulty of this problem is the basis for the security of several cryptographic systems, including Diffie–Hellman key agreement, ElGamal encryption
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
, the ElGamal signature scheme
ElGamal signature scheme
The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher ElGamal in 1984....
, the Digital Signature Algorithm
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...
, and the elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
analogs of these. Common choices for G used in these algorithms include the multiplicative group of integers modulo p, the multiplicative group of a finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
, and the group of points on an elliptic curve
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
modulo p or over a finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
.
Integers modulo p
On 18 Jun 2005, Antoine Joux and Reynald Lercier announced the computation of a discrete logarithm modulo a 130-digit (431-bit) strong primeStrong prime
In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.- Definition in cryptography :...
in three weeks, using a 1.15 GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.
On 5 Feb 2007 this was superseded by the announcement by Thorsten Kleinjung of the computation of a discrete logarithm modulo a 160-digit (530-bit) safe prime
Safe prime
A safe prime is a prime number of the form 2p + 1, where p is also a prime. The first few safe primes are...
, again using the number field sieve. Most of the computation was done using idle time on various PCs and on a parallel computing cluster.
Finite fields
The current record (as of 2010) in a finite field of characteristic 2 was announced by Antoine Joux and Reynald Lercier on 23 Sep 2005. They used the function field sieveFunction field sieve
In mathematics, the function field sieve was introduced in 1994 by Adleman as an efficient technique for extracting discrete logarithms over finite fields of small characteristic, and elaborated by Adleman and Huang in 1999....
to compute a discrete logarithm in a field of 2613 elements. The computation took 17 days on four 16-processor (1.3 GHz) nodes of the Itanium 2-based Bull computer Teranova.
The current record (as of 2010) for a field of characteristic 3 was announced by Takuya Hayashi et al., who computed a discrete logarithm in the field of 36 · 71 elements, using a variation on the function field sieve
Function field sieve
In mathematics, the function field sieve was introduced in 1994 by Adleman as an efficient technique for extracting discrete logarithms over finite fields of small characteristic, and elaborated by Adleman and Huang in 1999....
.
This also holds the record for the computation over the largest field (676 bits) of any type.
Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 6553725 elements (401 bits) announced on 24 Oct 2005, and in a field of 37080130 elements (556 bits) announced on 9 Nov 2005.
Elliptic curves
Certicom Corp. has issued a series of Elliptic Curve Cryptography challenges. Level I involves fields of 109-bit and 131-bit sizes. Level II includes 163, 191, 239, 359-bit sizes. All Level II challenges are currently believed to be computationally infeasible.The Level I challenges which have been met are:
- ECC2K-108, involving taking a discrete logarithm on a Koblitz curve over a field of 2108 elements. The prize was awarded on 4 April 2000 to a group of about 1300 people represented by Robert Harley. They used a parallelized Pollard rho methodPollard's rho algorithm for logarithmsPollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....
with speedup.
- ECC2-109, involving taking a discrete logarithm on a curve over a field of 2109 elements. The prize was awarded on 8 April 2004 to a group of about 2600 people represented by Chris Monico. They also used a version of a parallelized Pollard rho methodPollard's rho algorithm for logarithmsPollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....
, taking 17 months of calendar time.
- ECCp-109, involving taking a discrete logarithm on a curve modulo a 109-bit prime. The prize was awarded on 15 Apr 2002 to a group of about 10308 people represented by Chris Monico. Once again, they used a version of a parallelized Pollard rho methodPollard's rho algorithm for logarithmsPollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....
method, taking 549 days of calendar time.
None of the 131-bit (or larger) challenges have been met as of 2010.
In July 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery announced that they had carried out a discrete logarithm computation on an elliptic curve modulo a 112-bit prime. The computation was done on a cluster of over 200 PlayStation 3 game consoles over about 6 months. They used the common parallelized version of Pollard rho method
Pollard's rho algorithm for logarithms
Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....
.