Discrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions to the equation given elements and of a finite cyclic group . 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 used in these algorithms include the multiplicative group of integers modulo , the multiplicative group of a finite field, and the group of points on an elliptic curve over a finite field.
Integers modulo p The current 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, 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" 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 .
Previous records for integers modulo p include: 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.Emmanuel Thomé, "795-bit factoring and discrete logarithms," 2 December 2019.F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," 10 June 2020. 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.Thorsten Kleinjung, "Discrete logarithms in GF(p) – 768 bits," 16 June 2016. 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.Antoine Joux, "Discrete logarithms in GF(p) – 130 digits," 18 June 2005. 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.Thorsten Kleinjung, "Discrete logarithms in GF(p) – 160 digits," 5 February 2007. 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.Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé, "Discrete logarithms in GF(p) – 180 digits"
Also of note, in July 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome published their discrete logarithm computation on a 1024-bit prime.Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, "A kilobit hidden snfs discrete logarithm computation", IACR spring, July 2016 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 primesSize of primeType of primeDate announcedAnnounced byAlgorithmHardwareNotes240-digit (795-bit)safe prime2 December 2019 Fabrice Boudot Pierrick Gaudry Aurore Guillevic Nadia Heninger Emmanuel Thomé Paul Zimmermann number field sieveThe prime used was 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. Improvements in the algorithms and software made this computation about three times faster than would be expected from previous records after accounting for improvements in hardware. A paper providing details on the method was published in 2020.
The code required to reproduce this result is available at https://gitlab.inria.fr/cado-nfs/records/-/blob/master/dlp240/README.md.1024-bitJuly 2016 Joshua Fried Pierrick Gaudry Nadia Heninger Emmanuel Thomespecial number field sieveThe researchers generated a prime susceptible to the special number field sieve using a specialized algorithm on a comparatively small subgroup (160-bits).232-digit (768-bit)safe prime16 June 2016 Thorsten Kleinjung Claus Diem Arjen K. Lenstra Christine Priplata Colin Stahlkenumber field sieveThis computation started in February 2015.180 digit (596-bit)safe prime11 June 2014 Cyril Bouvier Pierrick Gaudry Laurent Imbert Hamza Jeljeli Emmanuel Thoménumber field sieve160-digit (530-bit) safe prime5 February 2007Thorsten Kleinjungnumber field sievevarious PCs, a parallel computing cluster130-digit (431-bit)strong prime18 June 2005 Antoine Joux Reynald Lerciernumber field sieve1.15 GHz 16-processor HP AlphaServer GS1280
Finite fields The current record () in a finite field of characteristic 2 was announced by Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski, and Jens Zumbrägel on 10 July 2019.Jens Zumbrägel, "Discrete Logarithms in GF(2^30750)", 10 July 2019, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907. This team was able to compute discrete logarithms in GF(230750) using 25,481,219 core hours on clusters based on the Intel Xeon architecture. This computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.R. Granger, T. Kleinjung, J. Zumbragel. On the discrete logarithm problem in finite fields of fixed characteristic. Trans. Amer. Math. Soc. 370, no. 5 (2018), pp. 3129-3145.
Previous records in a finite field of characteristic 2 were 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.Jens Zumbrägel, "Discrete Logarithms in GF(2^9234)", 31 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401. Antoine Joux on 21 May 2013. His team was able to compute discrete logarithms in the field with 26168 = (2257)24 elements using less than 550 CPU-hours. This computation was performed using the same index calculus algorithm as in the recent computation in the field with 24080 elements.Antoine Joux, "Discrete logarithms in GF(26168) [=GF((2257)24)]", 21 May 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034. Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbrägel on 11 Apr 2013. The new computation concerned the field with 26120 elements and took 749.5 core-hours. Antoine Joux on 22 March 2013. This used the same algorithmAntoine Joux. A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, 2013, http://eprint.iacr.org/2013/095 for small characteristic fields as the previous computation in the field with 21778 elements. The new computation concerned the field with 24080 elements, represented as a degree 255 extension of the field with 216 elements. The computation took less than 14100 core hours.Antoine Joux, "Discrete logarithms in GF(24080)", 22 Mar 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682. Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbrägel on 19 Feb 2013. They used a new variant of the medium-sized base field function field sieve, for binary fields, to compute a discrete logarithm in a field of 21971 elements. In order to use a medium-sized base field, they represented the field as a degree 73 extension of the field of 227 elements. The computation took 3132 core hours on an SGI Altix ICE 8200EX cluster using Intel (Westmere) Xeon E5650 hex-core processors.Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in , 2013, http://eprint.iacr.org/2013/074. Antoine Joux on 11 Feb 2013. This used a new algorithm for small characteristic fields. The computation concerned a field of 21778 elements, represented as a degree 127 extension of the field with 214 elements. The computation took less than 220 core hours.Antoine Joux, "Discrete logarithms in GF(21778)", 11 Feb. 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.
The current record () 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 in Granger, Robert, Thorsten Kleinjung, and Jens Zumbrägel. "Breaking `128-Bit Secure’ Supersingular Binary Curves (or How to Solve Discrete Logarithms in and )." arXiv:1402.3668 [cs, Math], 15 February 2014. https://arxiv.org/abs/1402.3668. with two main exceptions in the linear algebra computation and the descent phase. The total running time was less than four core years.Thorsten Kleinjung, 2014 October 17, "Discrete Logarithms in GF(2^1279)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410. The previous record in a finite field of characteristic 2 of prime degree was announced by the CARAMEL group on 6 April 2013. They used the function field sieve to compute a discrete logarithm in a field of 2809 elements.The CARAMEL group: Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann, "Discrete logarithm in GF(2809) with FFS", 6 April 2013, http://eprint.iacr.org/2013/197.
The current record () 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.Francisco Rodriguez-Henriquez, 18 July 2016, "Discrete Logarithms in GF(3^{6*509})", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8.1607.
Previous records in a finite field of characteristic 3 were announced: