Discrete logarithm records

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these 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 ${\displaystyle g^{x}=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 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.^{[citation needed]}

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 ${\displaystyle \mathrm {GF} (2^{30750})}$. When restricted to prime exponents^{[clarification needed]}, the current record, set in October 2014, is over ${\displaystyle \mathrm {GF} (2^{1279})}$. For characteristic 3, the current record, set in July 2016, is over ${\displaystyle \mathrm {GF} (3^{6*509})}$. For Kummer extension fields of "moderate"^{[clarification needed]} characteristic, the current record, set in January 2013, is over ${\displaystyle \mathrm {GF} (33341353^{57})}$. For fields of "moderate" characteristic (which are not necessarily Kummer extensions), the current record, published in 2022, is over ${\displaystyle \mathrm {GF} (2111023^{50})}$.^{[citation needed]}

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).