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 over a finite field.
Contents
Integers modulo p
On 16 June 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata, and Colin Stahlke announced the computation of a discrete logarithm modulo a 232-digit (768-bit) safe prime, using the number field sieve. The computation was started in February 2015 and took approximately 6600 core years scaled to an Intel Xeon E5-2660 at 2.2 GHz.
Previous records for integers modulo p include:
Finite fields
The current record (as of January 2014) in a finite field of characteristic 2 was announced by Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel on 31 January 2014. This team was able to compute discrete logarithms in GF(29234) using about 400,000 core hours. New features of this computation include a modified method for obtaining the logarithms of degree two elements and a systematically optimized descent strategy.
Previous records in a finite field of characteristic 2 were announced by:
The current record (as of 2014) in a finite field of characteristic 2 of prime degree was announced by Thorsten Kleinjung on 17 October 2014. The calculation was done in a field of 21279 elements and followed essentially the path sketched for
The current record (as of July 2016) for a field of characteristic 3 was announced by Gora Adj, Isaac Canales-Martinez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodriguez-Henriquez, and Luis Rivera-Zamarripa on 18 July 2016. The calculation was done in the 4841-bit finite field with 36 · 509 elements and was performed on several computers at CINVESTAV and the University of Waterloo. In total, about 200 core years of computing time was expended on the computation.
Previous records in a finite field of characteristic 3 were announced:
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 current record (as of 2013) for a finite field of "moderate" characteristic was announced on 6 January 2013. The team used a new variation of the function field sieve for the medium prime case to compute a discrete logarithm in a field of 3334135357 elements (a 1425-bit finite field). The same technique had been used a few weeks earlier to compute a discrete logarithm in a field of 3355377147 elements (an 1175-bit finite field).
On 25 June 2014, Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain announced 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).
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:
None of the 131-bit (or larger) challenges have been met as of 2016.
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.
In April 2014, Erich Wenger and Paul Wolfger from Graz University of Technology solved the discrete logarithm of a 113-bit Koblitz curve in extrapolated 24 days using an 18-core Virtex-6 FPGA cluster. In January 2015,the same researchers solved the discrete logarithm of an elliptic curve defined over a 113-bit binary field. The average runtime is around 82 days using a 10-core Kintex-7 FPGA cluster.
On 2 December 2016, Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann announced the solution of a generic 117.35-bit elliptic curve discrete logarithm problem on a binary curve, using an optimized FPGA implementation of a parallel version of Pollard's rho algorithm. The attack ran for about six months on 64 to 576 FPGAs in parallel.