Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Computation Of A 30750-Bit Binary Field Discrete Logarithm
 
research article

Computation Of A 30750-Bit Binary Field Discrete Logarithm

Granger, Robert  
•
Kleinjung, Thorsten  
•
Lenstra, Arjen K.  
Show more
November 1, 2021
Mathematics Of Computation

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbragel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about 2900 core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately 3100 core years expended for the discrete logarithm record for prime fields, set in a field of bit-length 795, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Grobner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the L(1/4 + o(1)) complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.

  • Details
  • Metrics
Type
research article
DOI
10.1090/mcom/3669
Web of Science ID

WOS:000691802800018

Author(s)
Granger, Robert  
Kleinjung, Thorsten  
Lenstra, Arjen K.  
Wesolowski, Benjamin  
Zumbraegel, Jens
Date Issued

2021-11-01

Publisher

AMER MATHEMATICAL SOC

Published in
Mathematics Of Computation
Volume

90

Issue

332

Start page

2997

End page

3022

Subjects

Mathematics, Applied

•

Mathematics

•

discrete logarithm problem

•

finite fields

•

binary fields

•

quasi-polynomial algorithm

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LACAL  
Available on Infoscience
September 11, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/181333
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés