This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
This article needs to be updated. The reason given is: It seems that some of these records have been surpassed. Please help update this article to reflect recent events or newly available information.(January 2022)
This article's lead section may be too short to adequately summarize the key points. Please consider expanding the lead to provide an accessible overview of all important aspects of the article. The reason given is: it doesn't describe what the current records for discrete logarithms are.(January 2022)
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details.(January 2022) (Learn how and when to remove this message)
(Learn how and when to remove this message)
This list (which may have dates, numbers, etc.) may be better in a sortable table format. Please help improve this list or discuss it on the talk page.(January 2022)
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 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 analogues 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.
The current[needs update] record for integers modulo prime numbers, set in December 2019, is a discrete logarithm computation modulo a prime with 240 digits. For characteristic 2, the current record for finite fields, set in July 2019, is a discrete logarithm over . When restricted to prime exponents[clarification needed], the current record, set in October 2014, is over . For characteristic 3, the current record, set in July 2016, is over . For Kummer extension fields of "moderate"[clarification needed] characteristic, the current record, set in January 2013, is over . For fields of "moderate" characteristic (which are not necessarily Kummer extensions), the current record, published in 2022, is over .
Integers modulo p
On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann announced the computation of a discrete logarithm modulo the 240-digit (795 bit) prime RSA-240 + 49204 (the first safe prime above RSA-240). This computation was performed simultaneously with the factorization of RSA-240, using the Number Field Sieve algorithm and the open-source CADO-NFS software. The discrete logarithm part of the computation took approximately 3100 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1 GHz). The researchers estimate that improvements in the algorithms and software made this computation three times faster than would be expected from previous records after accounting for improvements in hardware.[1][2]
Previous records for integers modulo p include:
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.[3]
On 18 June 2005, Antoine Joux and Reynald Lercier announced the computation of a discrete logarithm modulo a 130-digit (431-bit) strong prime in three weeks, using a 1.15 GHz 16-processor HP AlphaServer GS1280 computer and a number field sieve algorithm.[4]
On 5 February 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.[5]
On 11 June 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé announced the computation of a discrete logarithm modulo a 180 digit (596-bit) safe prime using the number field sieve algorithm.[6]
Also of note, in July 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome published their discrete logarithm computation on a 1024-bit prime.[7] They generated a prime susceptible to the special number field sieve, using the specialized algorithm on a comparatively small subgroup (160-bits). While this is a small subgroup, it was the standardized subgroup size used with the 1024-bit digital signature algorithm (DSA).
Discrete logarithm records modulo primes
Size of prime
Type of prime
Date announced
Announced by
Algorithm
Hardware
Notes
240-digit (795-bit)
safe prime
2 December 2019
Fabrice Boudot
Pierrick Gaudry
Aurore Guillevic
Nadia Heninger
Emmanuel Thomé
Paul Zimmermann
number field sieve
The prime used was RSA-240 + 49204 (the first safe prime above RSA-240). This computation was performed simultaneously[how?] with the factorization of RSA-240, using the Number Field Sieve algorithm and the open-source CADO-NFS software. Improvements in the algorithms and software[which?] made this computation about three times faster than would be expected from previous records after accounting for improvements in hardware.
1024-bit
July 2016
Joshua Fried
Pierrick Gaudry
Nadia Heninger
Emmanuel Thome
special number field sieve
The researchers generated a prime susceptible[why?] to the special number field sieve[how?] using a specialized algorithm[which?] on a comparatively small subgroup (160-bits).
232-digit (768-bit)
safe prime
16 June 2016
Thorsten Kleinjung
Claus Diem
Arjen K. Lenstra
Christine Priplata
Colin Stahlke
number field sieve
This computation started in February 2015.
180 digit (596-bit)
safe prime
11 June 2014
Cyril Bouvier
Pierrick Gaudry
Laurent Imbert
Hamza Jeljeli
Emmanuel Thomé
number field sieve
160-digit (530-bit)
safe prime
5 February 2007
Thorsten Kleinjung
number field sieve
various PCs, a parallel computing cluster[which?]
130-digit (431-bit)
strong prime
18 June 2005
Antoine Joux
Reynald Lercier
number field sieve
1.15 GHz 16-processor HP AlphaServer GS1280
^Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.
^F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," June 10, 2020.
^Thorsten Kleinjung, “Discrete logarithms in GF(p) – 768 bits,” June 16, 2016.
^Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005.[dead link]
^Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007.
^Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel
Thomé, "Discrete logarithms in GF(p) – 180 digits"
Discretelogarithmrecords are the best results achieved to date in solving the discretelogarithm problem, which is the problem of finding solutions x...
algorithm is a probabilistic algorithm for computing discretelogarithms. Dedicated to the discretelogarithm in ( Z / q Z ) ∗ {\displaystyle (\mathbb {Z} /q\mathbb...
prime above RSA-240) using a number field sieve algorithm; see Discretelogarithmrecords. There is no special primality test for safe primes the way there...
factorization and discretelogarithm: a 240-digit experiment," June 10, 2020. "LISTSERV - NMBRTHRY Archives - LISTSERV.NODAK.EDU". P. L. Montgomery. "Record Number...
sense, it also includes exponentiation, extraction of roots, and taking logarithms. Arithmetic systems can be distinguished based on the type of number they...
symbolic notation by François Viète (1540–1603), the introduction of logarithms by John Napier in 1614, which greatly simplified numerical calculations...
William Oughtred, shortly after the publication of the concept of the logarithm. It is a hand-operated analog computer for doing multiplication and division...
Algorithm's design is based on the DH ratchet that was introduced by Off-the-Record Messaging (OTR) and combines it with a symmetric-key ratchet modeled after...
similar to slide rules, but employing unique, discrete "Logarithmic Indexes" (now known as Irish logarithms), as well as a novel memory system utilizing...
1\right]} in the L-notation. The constant e is the base of the natural logarithm. To factorize the integer n, Fermat's method entails a search for a single...
signature scheme on its own does not prevent a valid signed message from being recorded and then maliciously reused in a replay attack. For example, the branch...
{\displaystyle a^{b}{\bmod {c}}} ), while the reverse operation (the discretelogarithm) is thought to be a hard problem. Prime numbers are frequently used...
The first version of the protocol, TextSecure v1, was based on Off-the-record messaging (OTR). On 24 February 2014, Open Whisper Systems introduced TextSecure...
one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of ( x 0 − x 1 ) {\displaystyle...
procedure, and the security of each relies on the difficulty of the discretelogarithm problem, just as the above does. All sent values also include zero-knowledge...
PGP/GPG Keys and fingerprints can also be added into a server's DNSSEC DNS records. So any users who want to communicate securely (or any software users)...
transform on R or Rn, notably includes the discrete-time Fourier transform (DTFT, group = Z), the discrete Fourier transform (DFT, group = Z mod N) and...
arithmetic; when computing mathematical functions such as square roots, logarithms, and sines; or when using a floating-point representation with a fixed...
particles, in which he defined entropy as proportional to the natural logarithm of the number of microstates such a gas could occupy. The proportionality...
fingerprint (or the key it refers to) will be stored locally along with a record of the other user's name or address, so that future communications with...