Computation of a 30750-bit binary field discrete logarithm

DOI10.1090/MCOM/3669zbMATH Open1472.11319arXiv2008.02717OpenAlexW3165713929MaRDI QIDQ4956935FDOQ4956935

Authors: Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra, Benjamin Wesolowski, Jens Zumbrägel 

Publication date: 2 September 2021

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: This paper reports on the computation of a discrete logarithm in the finite field $mathbb{F}_{2^{30750}}$, breaking by a large margin the previous record, which was set in January 2014 by a computation in $mathbb{F}_{2^{9234}}$. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbr"agel, 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 Gr"obner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the $L(frac14+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.

Full work available at URL: https://arxiv.org/abs/2008.02717

Recommendations

• Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
• Solving a $$6120$$ -bit DLP on a Desktop Computer
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• scientific article; zbMATH DE number 2081061
• New discrete logarithm computation for the medium prime case using the function field sieve

zbMATH Keywords

discrete logarithm problemfinite fieldsbinary fieldsquasi-polynomial algorithm

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• The Magma algebra system. I: The user language
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• On \(x^{q+1}+ax+b\)
• Factorization of a 768-Bit RSA Modulus
• Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in \({\mathbb F}_{2^{4 \cdot 1223}}\) and \({\mathbb F}_{2^{12 \cdot 367}}\))
• Fast evaluation of logarithms in fields of characteristic two
• Title not available (Why is that?)
• Finding Isomorphisms Between Finite Fields
• A general framework for subexponential discrete logarithm algorithms
• Modifications to the number field sieve
• Improved Masking for Tweakable Blockciphers with Applications to Authenticated Encryption
• Solving a $$6120$$ -bit DLP on a Desktop Computer
• Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
• On the discrete logarithm problem in finite fields of fixed characteristic
• Computation of a 768-Bit Prime Field Discrete Logarithm
• Mersenne Factorization Factory
• Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression

Cited In (4)

• Title not available (Why is that?)
• A survey of elliptic curves for proof systems
• Roots of certain polynomials over finite fields
• A Kilobit Hidden SNFS Discrete Logarithm Computation

Uses Software

• Magma

This page was built for publication: Computation of a 30750-bit binary field discrete logarithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956935)