View source for Discrete logarithm records

{{Short description|Best results achieved to date}}
{{Multiple issues|
{{Update|date=January 2022|reason=It seems that some of these records have been surpassed}}
{{Lead too short|date=January 2022|reason=it doesn't describe what the current records for discrete logarithms are.}}
{{Technical|date=January 2022}}
}}
{{List to table|date=January 2022}}

{{Use dmy dates|date=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 <math>g^x = h</math> given elements ''g'' and ''h'' of a [[finite group|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 [[algorithm]]s include the multiplicative [[group (mathematics)|group]] of [[integer]]s [[modular arithmetic|modulo]] ''p'', the multiplicative group of a [[finite field]], and the group of points on an [[elliptic curve]] over a finite field.{{Needs source|date=October 2024}}

The current{{Update inline|date=January 2022|reason=Please check whether any of these records have been surpassed.}} record for integers modulo [[prime number]]s, set in December 2019, is a discrete logarithm computation modulo a prime with 240 digits. For [[characteristic (algebra)|characteristic]] 2, the current record for finite fields, set in July 2019, is a discrete logarithm over <math>\mathrm{GF}(2^{30750})</math>. When restricted to prime exponents{{Clarify|date=January 2022}}, the current record, set in October 2014, is over <math>\mathrm{GF}(2^{1279})</math>. For characteristic 3, the current record, set in July 2016, is over <math>\mathrm{GF}(3^{6*509})</math>. For Kummer extension [[field (mathematics)|field]]s of "moderate"{{Clarify|date=January 2022}} characteristic, the current record, set in January 2013, is over <math>\mathrm{GF}(33341353^{57})</math>. For fields of "moderate" characteristic (which are not necessarily Kummer extensions), the current record, published in 2022, is over <math> \mathrm {GF} (2111023^{50})</math>.{{Needs source|date=October 2024}}

'''Integers modulo ''p'''''

* On 2 Dec 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, [[Nadia Heninger]], Emmanuel Thomé, and [[Paul Zimmermann (mathematician)|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 [[integer factorization|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&nbsp;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.<ref>Emmanuel Thomé, [https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912 “795-bit factoring and discrete logarithms,”] December 2, 2019.</ref><ref>F. Boudot et al, [https://eprint.iacr.org/2020/697 "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment,"] June 10, 2020.</ref>

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&nbsp;GHz.<ref>Thorsten Kleinjung, [https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;a0c66b63.1606 “Discrete logarithms in GF(''p'') – 768 bits,”] June 16, 2016.</ref>
* 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&nbsp;GHz 16-processor HP [[AlphaServer GS1280]] computer and a [[General number field sieve|number field sieve]] algorithm.<ref>Antoine Joux, [http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=20 “Discrete logarithms in GF(''p'') – 130 digits,”] June 18, 2005.{{Dead link|date=January 2022}}</ref>
* 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.<ref>Thorsten Kleinjung, [http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0 “Discrete logarithms in GF(''p'') – 160 digits,”] February 5, 2007.</ref>
* 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.<ref>Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel
Thomé, [https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=3161 "Discrete logarithms in GF(''p'') – 180 digits"]</ref>

Also of note, in July 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome published their discrete logarithm computation on a 1024-bit prime.<ref>Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, [https://eprint.iacr.org/2016/961.pdf “A kilobit hidden snfs discrete logarithm computation”], IACR spring, July 2016</ref> 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).
{| class="wikitable sortable"
|+Discrete logarithm records modulo primes
!Size of prime
!Type of prime
!Date announced
!Announced by
!Algorithm
!Hardware
!Notes
|-
|240-digit (795-bit)
|[[safe prime]]
|data-sort-value="2019-12-02" |2 December 2019
|
* Fabrice Boudot
* Pierrick Gaudry
* Aurore Guillevic
* [[Nadia Heninger]]
* Emmanuel Thomé
* [[Paul Zimmermann (mathematician)|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|date=January 2022}} 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|date=January 2022}} made this computation about three times faster than would be expected from previous records after accounting for improvements in hardware.
|-
|1024-bit
|
|data-sort-value="2016-07-01" |July 2016
|
* Joshua Fried
* Pierrick Gaudry
* Nadia Heninger
* Emmanuel Thome
|special number field sieve
|
|The researchers generated a prime susceptible{{Why|date=January 2022}} to the special number field sieve{{How|date=January 2022}} using a specialized algorithm{{Which|date=January 2022}} on a comparatively small subgroup (160-bits).
|-
|232-digit (768-bit)
|safe prime
|data-sort-value="2016-06-16" |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
|data-sort-value="2014-06-11" |11 June 2014
|
* Cyril Bouvier
* Pierrick Gaudry
* Laurent Imbert
* Hamza Jeljeli
* Emmanuel Thomé
|number field sieve
|
|
|-
|160-digit (530-bit) 
|safe prime
|data-sort-value="2007-02-05" |5 February 2007
|Thorsten Kleinjung
|number field sieve
|various PCs, a parallel computing cluster{{Which|date=January 2022}}
|
|-
|130-digit (431-bit)
|[[strong prime]]
|data-sort-value="2005-06-18" |18 June 2005
|
* [[Antoine Joux]]
* Reynald Lercier
|number field sieve
|1.15&nbsp;GHz 16-processor HP [[AlphaServer GS1280]]
|
|}

==Finite fields==
The current record ({{As of|2019|7|alt=as of July 2019}}) 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.<ref>Jens Zumbrägel, "Discrete Logarithms in GF(2^30750)", 10 July 2019, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907.</ref> This team was able to compute discrete logarithms in GF(2<sup>30750</sup>) 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.<ref>R. Granger, T. Kleinjung, J. Zumbragel.  [https://web.archive.org/web/20240428084403/https://www.ams.org/journals/tran/2018-370-05/S0002-9947-2017-07027-6/S0002-9947-2017-07027-6.pdf On the discrete logarithm problem in finite fields of fixed characteristic].  Trans. Amer. Math.
Soc. 370, no. 5 (2018), pp. 3129-3145.</ref>

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(2<sup>9234</sup>) 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.<ref>Jens Zumbrägel, "Discrete Logarithms in GF(2^9234)", 31 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.</ref>
* Antoine Joux on 21 May 2013. His team was able to compute discrete logarithms in the field with 2<sup>6168</sup> = (2<sup>257</sup>)<sup>24</sup> 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 2<sup>4080</sup> elements.<ref>Antoine Joux, "Discrete logarithms in GF(2<sup>6168</sup>) [=GF((2<sup>257</sup>)<sup>24</sup>)]", May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.</ref>
* Robert Granger, Faruk Göloğlu, Gary McGuire, and Jens Zumbrägel on 11 Apr 2013. The new computation concerned the field with 2<sup>6120</sup> elements and took 749.5 core-hours.
* Antoine Joux on Mar 22nd, 2013. This used the same algorithm<ref>Antoine Joux. A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, 2013, http://eprint.iacr.org/2013/095</ref> for small characteristic fields as the previous computation in the field with 2<sup>1778</sup> elements. The new computation concerned the field with 2<sup>4080</sup> elements, represented as a degree 255 [[field extension|extension]] of the field with 2<sup>16</sup> elements. The computation took less than 14100 core hours.<ref>Antoine Joux, "Discrete logarithms in GF(2<sup>4080</sup>)", Mar 22, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682.</ref>
* 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 2<sup>1971</sup> elements. In order to use a medium-sized base field, they represented the field as a degree 73 extension of the field of 2<sup>27</sup> elements. The computation took 3132 core hours on an SGI Altix ICE 8200EX cluster using Intel (Westmere) Xeon E5650 hex-core processors.<ref>Faruk Gologlu et al.,  On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in <math>\mathbb{F}_{2^{1971}}</math>, 2013, http://eprint.iacr.org/2013/074.</ref>
* Antoine Joux on 11 Feb 2013. This used a new algorithm for small characteristic fields. The computation concerned a field of 2<sup>1778</sup> elements, represented as a degree 127 extension of the field with 2<sup>14</sup> elements. The computation took less than 220 core hours.<ref>Antoine Joux, "Discrete logarithms in GF(2<sup>1778</sup>)", Feb. 11, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.</ref>

The current record ({{As of|2014|alt=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 2<sup>1279</sup> elements and followed essentially the path sketched for <math>\mathrm{GF}(2^{4 \cdot 1223})</math> in <ref>Granger, Robert, Thorsten Kleinjung, and Jens Zumbrägel. “Breaking `128-Bit Secure’ Supersingular Binary Curves (or How to Solve Discrete Logarithms in <math>{\mathbb F}_{2^{4 \cdot 1223}}</math> and <math>{\mathbb F}_{2^{12 \cdot 367}}</math>).” arXiv:1402.3668 [cs, Math], February 15, 2014. https://arxiv.org/abs/1402.3668.</ref> with two main exceptions in the [[linear algebra]] computation and the descent phase. The total running time was less than four core years.<ref>Thorsten Kleinjung, 2014 October 17, "Discrete Logarithms in GF(2^1279)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410.</ref> The previous record in a finite field of characteristic 2 of prime degree was announced by the CARAMEL group on April 6, 2013. They used the [[function field sieve]] to compute a discrete logarithm in a field of 2<sup>809</sup> elements.<ref>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(2<sup>809</sup>) with FFS”, April 6, 2013, http://eprint.iacr.org/2013/197.</ref>

The current record ({{As of|2016|7|alt=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 3<sup>6&thinsp;·&thinsp;509</sup> 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.<ref>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.</ref>

Previous records in a finite field of characteristic 3 were announced:

* in the full version of the Asiacrypt 2014 paper of Joux and Pierrot (December 2014).<ref>{{Cite web|last1=Joux|first1=Antoine|last2=Pierrot|first2=Cécile|title=Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms|url=http://www-polsys.lip6.fr/~pierrot/papers/Simplified%20Frob%20Rep.pdf|url-status=dead|archive-url=https://web.archive.org/web/20141211051755/http://www-polsys.lip6.fr/~pierrot/papers/Simplified%20Frob%20Rep.pdf|archive-date=2014-12-11|access-date=2014-12-11}}</ref> The DLP is solved in the field GF(3<sup>5&thinsp;·&thinsp;479</sup>), which is a 3796-bit field. This work did not exploit any "special" aspects of the field such as Kummer or twisted-Kummer properties. The total computation took less than 8600 CPU-hours.
* by Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez on 26 February 2014, updating a previous announcement on 27 January 2014. The computation solve DLP in the 1551-bit field GF(3<sup>6&thinsp;·&thinsp;163</sup>), taking 1201 CPU hours.<ref>Francisco Rodríguez-Henríquez, “Announcement,” 27 January 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401.</ref><ref>Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodríguez-Henríquez, "Computing Discrete Logarithms in F_{3^{6*137}} and F_{3^{6*163}} using Magma", 26 Feb 2014, http://eprint.iacr.org/2014/057.</ref>
* in 2012 by a joint Fujitsu, NICT, and Kyushu University team, that computed a discrete logarithm in the field of 3<sup>6&thinsp;·&thinsp;97</sup> elements and a size of 923 bits,<ref>Kyushu University, NICT and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography, 2012, http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf.</ref> using a variation on the [[function field sieve]] and beating the previous record in a field of 3<sup>6&thinsp;·&thinsp;71</sup> elements and size of 676 bits by a wide margin.<ref>Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(3<sup>6''n''</sup>), 2010, http://eprint.iacr.org/2010/090.</ref>

Over fields of "moderate"-sized characteristic, notable computations as of 2005 included those a field of 65537<sup>25</sup> elements (401 bits) announced on 24 Oct 2005, and in a field of 370801<sup>30</sup> elements (556 bits) announced on 9 Nov 2005.<ref>A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf {{Webarchive|url=https://web.archive.org/web/20110710202518/http://eric-diehl.com/letter/Newsletter1_Final.pdf |date=2011-07-10 }}.</ref> The current record (as of 2013) for a Kummer extension 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 Kummer extension field of 33341353<sup>57</sup> elements (a 1425-bit finite field).<ref>Antoine Joux, “Discrete Logarithms in a 1425-bit Finite Field,” January 6, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214.</ref><ref name="Joux-ePrint">Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields,   Eprint Archive, http://eprint.iacr.org/2012/720</ref> The same technique had been used a few weeks earlier to compute a discrete logarithm in a Kummer extension field of 33553771<sup>47</sup> elements (an 1175-bit finite field).<ref  name="Joux-ePrint"/><ref>Antoine Joux, “Discrete Logarithms in a 1175-bit Finite Field,” December 24, 2012, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902<nowiki/>.{{Dead link|date=January 2022}}</ref> The current record (as of 2022) for a finite field of "moderate" characteristic (which is not necessarily a Kummer extension) is the computation of discrete logarithm in a field of 2111023<sup>50</sup> elements (a 1051-bit finite field);<ref>{{cite journal|last1=Mukhopadhyay|first1=Madhurima|last2=Sarkar|first2=Palash|last3=Singh|first3=Shashank|last4=Thomé|first4=Emmanuel|title=New discrete logarithm computation for the medium prime case using the function field sieve|journal=Advances in Mathematics of Communications|year=2022|volume=16 |issue=3 |page=449 |url=https://www.aimsciences.org/article/doi/10.3934/amc.2020119|doi=10.3934/amc.2020119|doi-access=free}}</ref> previous record<ref>{{cite journal|last1=Sarkar|first1=Palash|last2=Singh|first2=Shashank|title=Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case|journal=IEEE Transactions on Information Theory|year=2016|volume=62 |issue=4 |pages=2233–2253 |url=https://ieeexplore.ieee.org/document/7405328|doi=10.1109/TIT.2016.2528996}}</ref> of discrete logarithm computations over such fields was over fields having 297079<sup>40</sup> elements (a 728-bit
finite field) and 64373<sup>37</sup> elements (a 592-bit finite field). These computations were done using new ideas to speed up the function field sieve.

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.<ref name=":0">Razvan Barbulescu, “Discrete logarithms in GF(p^2) --- 160 digits,” June 24, 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c.1406.</ref> 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).
{| class="wikitable sortable"
|+Discrete logarithm records over finite fields
!Char.
!Field size
!Date announced
!Announced by
!Hardware
!Compute
!Notes
|-
| rowspan="9" |2
|2<sup>30750</sup>
|data-sort-value="2019-07-10" |10 July 2019
|
* Robert Granger
* Thorsten Kleinjung
* Arjen Lenstra
* Benjamin Wesolowski
* Jens Zumbrägel
|[[Intel Xeon]] architecture
|25,481,219 core-hours
|This computation was the first large-scale example using the elimination step of the quasi-polynomial algorithm.{{Clarify|date=January 2022}}
|-
|2<sup>1279</sup>
|data-sort-value="2014-10-17" |17 October 2014
|Thorsten Kleinjung
|
|<4 core-years
|
|-
|2<sup>9234</sup>
|data-sort-value="2014-01-31" |31 January 2014
|
* Robert Granger
* Thorsten Kleinjung
* Jens Zumbrägel
|
|~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.{{Clarify|date=January 2022}}
|-
|2<sup>6168</sup>
|data-sort-value="2013-05-21" |21 May 2013
|Antoine Joux
|
|<550 CPU-hours{{Quantify|date=January 2022}}
|
|-
|2<sup>6120</sup>
|data-sort-value="2013-04-11" |11 April 2013
|
* Robert Granger 
* Faruk Göloğlu
* Gary McGuire 
* Jens Zumbrägel
|
|749.5 core-hours
|
|-
|2<sup>809</sup>
|data-sort-value="2013-04-06" |6 April 2013
|the CARAMEL group{{Who|date=January 2022}}
|
|
|
|-
|2<sup>4080</sup>
|data-sort-value="2013-03-22" |22 March 2013
|Antoine Joux
|
|<14,100 core-hours{{Quantify|date=January 2022}}
|
|-
|2<sup>1971</sup>
|data-sort-value="2013-02-19" |19 February 2013
|
* Robert Granger
* Faruk Göloğlu 
* Gary McGuire
* Jens Zumbrägel
|SGI Altix ICE 8200EX cluster

Intel (Westmere) Xeon E5650 hex-core processors
|3,132 core-hours
|
|-
|2<sup>1778</sup>
|data-sort-value="2013-02-11" |11 February 2013
|Antoine Joux
|
|<220 core-hours{{Quantify|date=January 2022}}
|
|-
| rowspan="5" |3
|3<sup>6&nbsp;·&nbsp;509</sup>
|data-sort-value="2016-07-18" |18 July 2016
|
* Gora Adj
* Isaac Canales-Martinez
* Nareli Cruz-Cortés
* Alfred Menezes
* Thomaz Oliveira
* Francisco Rodriguez-Henriquez
* Luis Rivera-Zamarripa
|several computers{{Which|date=January 2022}} at [[CINVESTAV]] and the [[University of Waterloo]]
|~200 core-years
|
|-
|3<sup>5&nbsp;·&nbsp;479</sup>
|data-sort-value="2014-12-01" |December 2014
|
* Antoine Joux
* Cécile Pierrot
|
|<8600 CPU-hours{{Quantify|date=January 2022}}
|
|-
|3<sup>6&nbsp;·&nbsp;163</sup>
|data-sort-value="2014-01-27" |27 January 2014
|
* Gora Adj
* Alfred Menezes
* Thomaz Oliveira
* Francisco Rodríguez-Henríquez
|
|1201 CPU-hours
|
|-
|3<sup>6&nbsp;·&nbsp;97</sup>
|data-sort-value="2012-01-01" |2012
|a joint Fujitsu, NICT, and Kyushu University team{{Who|date=January 2022}}
|
|
|
|-
|3<sup>6&nbsp;·&nbsp;71</sup>
|
|
|
|
|
|-
| rowspan="5" |"moderate"
|''p''<sup>2</sup>
|data-sort-value="2014-06-25" |25 June 2014
|
* Razvan Barbulescu
* Pierrick Gaudry
* Aurore Guillevic
* François Morain
|
|68 CPU-days + 30 GPU-hours
|This field is a degree-2 extension of a prime field, where ''p'' is a prime with 80 digits.<ref name=":0" />
|-
|33341353<sup>57</sup>
|data-sort-value="2013-01-06" |6 January 2013
|
|
|
|
|-
|33553771<sup>47</sup>
|
|
|
|
|
|-
|370801<sup>30</sup>
|data-sort-value="2005-11-09" |9 November 2005
|
|
|
|
|-
|65537<sup>25</sup>
|data-sort-value="2005-10-24" |24 October 2005
|
|
|
|
|}

==Elliptic curves==
[[Certicom]] Corp. has issued a series of [[Elliptic-curve cryptography|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.<ref>Certicom Corp., “The Certicom ECC Challenge,” https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html</ref>

The Level I challenges which have been met are:<ref>Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), {{cite web |url=http://www.certicom.com/images/pdfs/challenge-2009.pdf |title=Archived copy |accessdate=2010-12-30 |url-status=dead |archiveurl=https://web.archive.org/web/20151022135946/https://www.certicom.com/images/pdfs/challenge-2009.pdf |archivedate=2015-10-22 }} .</ref>

* ECC2K-108, involving taking a discrete logarithm on a [[Koblitz curve]] over a field of 2<sup>108</sup> 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's rho algorithm for logarithms|Pollard rho method]] with speedup.
* ECC2-109, involving taking a discrete logarithm on a curve over a field of 2<sup>109</sup> 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 method, 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 method, taking 549 days of calendar time.

None of the 131-bit (or larger) challenges have been met {{As of|2019|alt=as of 2019}}.

In July 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra and [[Peter Montgomery (mathematician)|Peter L. Montgomery]] announced that they had carried out a discrete logarithm computation on an elliptic curve (known as secp112r1<ref>Certicom Research, "SEC 2: Recommended Elliptic Curve Domain Parameters" https://www.secg.org/SEC2-Ver-1.0.pdf</ref>) 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.<ref>Joppe W. Bos and Marcelo E. Kaihara, “PlayStation 3 computing breaks 2^60 barrier:  112-bit prime ECDLP solved,” EPFL Laboratory for cryptologic algorithms - LACAL, http://lacal.epfl.ch/112bit_prime</ref>

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{{Refn|The computation ran for 47 days, but not all of the FPGAs used were active all the time, which meant that it was equivalent to an extrapolated time of 24 days.|group=note|name=extrapolated47to24}} 24 days using an 18-core [[Virtex-6]] [[Field-programmable gate array|FPGA]] cluster.<ref name=":1">Erich Wenger and Paul Wolfger, “Solving the Discrete Logarithm of a 113-bit Koblitz Curve with an FPGA Cluster” http://eprint.iacr.org/2014/368</ref> 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]] [[Field-programmable gate array|FPGA]] cluster.<ref>Erich Wenger and Paul Wolfger, “Harder, Better, Faster, Stronger - Elliptic Curve Discrete Logarithm Computations on FPGAs” http://eprint.iacr.org/2015/143/</ref>

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 method. The attack ran for about six months on 64 to 576 FPGAs in parallel.<ref>Ruben Niederhagen, “117.35-Bit ECDLP on Binary Curve,” https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612</ref>

On 23 August 2017, Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai, and Sylvain Duquesne announced that they had solved a discrete logarithm problem on a 114-bit "pairing-friendly" Barreto–Naehrig (BN) curve,<ref>{{cite web|date=23 August 2017|title=114-bit ECDLP on a BN curve has been solved|url=http://isec.ec.okayama-u.ac.jp/whats-new/114-bit-ecdlp-has-been-solved|url-status=dead|archive-url=https://web.archive.org/web/20180527201520/http://isec.ec.okayama-u.ac.jp/whats-new/114-bit-ecdlp-has-been-solved/|archive-date=27 May 2018|website=isec.ec.okayama-u.ac.jp|accessdate=2018-05-03}}</ref> using the special sextic twist property of the BN curve to efficiently carry out the random walk of Pollard's rho method. The implementation used 2000 CPU cores and took about 6 months to solve the problem.<ref>{{cite conference |title= Solving 114-Bit ECDLP for a Barreto–Naehrig Curve|last1=Kusaka |first1=Takuya  |last2=Joichi |first2= Sho |first3=Ken|last3= Ikuta|first4= Md. Al-Amin |last4=Khandaker|first5= Yasuyuki|last5= Nogami| first6=Satoshi|last6= Uehara|first7= Nariyoshi |last7=Yamai| first8= Sylvain|last8= Duquesne|series=Lecture Notes in Computer Science |date=2018 |volume=10779 |publisher= Springer|book-title=Information Security and Cryptology – ICISC 2017 |pages= 231–244|doi= 10.1007/978-3-319-78556-1_13|isbn=978-3-319-78555-4 |url= https://hal.archives-ouvertes.fr/hal-01633653/file/article.pdf}}</ref>

On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons ([https://github.com/JeanLucPons JeanLucPons]) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software<ref>{{cite web | title=Pollard's kangaroo for SECPK1 | first1=Jean-Luc |last1=Pons | first2=Aleksander | last2=Zieniewicz | website=[[GitHub]] | date=17 January 2022 | url=https://github.com/JeanLucPons/Kangaroo}}</ref> based on the [[Pollard's kangaroo algorithm|Pollard Kangaroo]] on 256x [https://www.nvidia.com/en-us/data-center/v100/ NVIDIA Tesla V100] GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.
{| class="wikitable"
|+Discrete logarithm records for elliptic curves
!Curve name
!Field size
!Date announced
!Announced by
!Algorithm
!Compute time
|-
|ECC2K-108
|2<sup>108</sup>
|2000
|about 1300 people represented by Robert Harley
|[[Pollard's rho algorithm for logarithms|Pollard rho method]]
|
|-
|ECCp-109
|a 109-bit prime
|2002
|about 10308 people represented by Chris Monico
|parallelized Pollard rho method
|549 days
|-
|ECC2-109
|2<sup>109</sup>
|2004
|about 2600 people represented by Chris Monico
|parallelized Pollard rho method
|17 months
|-
|secp112r1
|a 112-bit prime
|July 2009
|
* Joppe W. Bos
* Marcelo E. Kaihara
* Thorsten Kleinjung
* Arjen K. Lenstra
* [[Peter Montgomery (mathematician)|Peter L. Montgomery]]
|the common parallelized version of Pollard rho method{{Which|date=January 2022}}
|6 months
|-
|
|2<sup>113</sup>
|April 2014
|
* [[Erich Wenger]]
* [[Paul Wolfger]]
|
|47 days<ref name=":1" />{{Refn|group=note|name=extrapolated47to24}}
|-
|
|2<sup>113</sup>
|January 2015
|
* [[Erich Wenger]]
* [[Paul Wolfger]]
|
|82 days{{Verify source|date=January 2022|reason="average runtime" = runtime?}}
|-
|
|2<sup>127</sup>
Interval search size 2<sup>117.35</sup>
|2 December 2016
|
* [[Daniel J. Bernstein]]
* [[Susanne Engels]]
* [[Tanja Lange]]
* [[Ruben Niederhagen]]
* [[Christof Paar]]
* [[Peter Schwabe]]
* [[Ralf Zimmermann]]
|parallel version of Pollard's rho method
|6 months of 64 to 576 FPGAs 
|-
|Barreto–Naehrig Pairing friendly curve
|2<sup>114</sup>
|23 August 2017
|
* Takuya Kusaka
* Sho Joichi
* Ken Ikuta
* Md. Al-Amin Khandaker
* Yasuyuki Nogami
* Satoshi Uehara
* Nariyoshi Yamai
* Sylvain Duquesne
|parallel version of Pollard's rho method on twisted BN curve
|6 months using 2000 CPU
|-
|secp256k1
|2<sup>256</sup> 
Interval search size 2<sup>114</sup>
|16 August 2020
|
* Aleksander Zieniewicz
* Jean Luc Pons
| parallel version of Pollard's rho method
| 13 Days on 256xTesla V100
|}

== Notes ==
{{reflist|group=note}}

== References ==
{{reflist}}

== External links ==
*[https://dldb.loria.fr/ Computations of discrete logarithms sorted by date]

[[Category:Asymmetric-key algorithms]]
[[Category:Modular arithmetic]]
[[Category:Logarithms]]
[[Category:Computational hardness assumptions]]
[[Category:World records]]