Computation of a 30750-bit binary field discrete logarithm
From MaRDI portal
Publication:4956935
Abstract: This paper reports on the computation of a discrete logarithm in the finite field , breaking by a large margin the previous record, which was set in January 2014 by a computation in . 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 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.
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
Cites work
- scientific article; zbMATH DE number 503245 (Why is no real title available?)
- A general framework for subexponential discrete logarithm algorithms
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic
- 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}}\))
- Computation of a 768-bit prime field discrete logarithm
- Factorization of a 768-Bit RSA Modulus
- Fast evaluation of logarithms in fields of characteristic two
- Finding Isomorphisms Between Finite Fields
- Improved Masking for Tweakable Blockciphers with Applications to Authenticated Encryption
- Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
- Mersenne factorization factory
- Modifications to the number field sieve
- On \(x^{q+1}+ax+b\)
- On the discrete logarithm problem in finite fields of fixed characteristic
- 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}}\)
- Solving a $$6120$$ -bit DLP on a Desktop Computer
- Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression
- The Magma algebra system. I: The user language
Cited in
(5)- Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
- scientific article; zbMATH DE number 2081061 (Why is no real title available?)
- A survey of elliptic curves for proof systems
- Roots of certain polynomials over finite fields
- A Kilobit Hidden SNFS Discrete Logarithm Computation
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)
