Indiscreet logarithms in finite fields of small characteristic
From MaRDI portal
Abstract: Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.
Recommendations
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- Computing discrete logarithms
- On the discrete logarithm problem in finite fields of fixed characteristic
Cites work
- scientific article; zbMATH DE number 1643939 (Why is no real title available?)
- scientific article; zbMATH DE number 3956969 (Why is no real title available?)
- scientific article; zbMATH DE number 4077312 (Why is no real title available?)
- scientific article; zbMATH DE number 1244209 (Why is no real title available?)
- scientific article; zbMATH DE number 1313469 (Why is no real title available?)
- scientific article; zbMATH DE number 503245 (Why is no real title available?)
- scientific article; zbMATH DE number 708814 (Why is no real title available?)
- scientific article; zbMATH DE number 1142300 (Why is no real title available?)
- scientific article; zbMATH DE number 2081083 (Why is no real title available?)
- scientific article; zbMATH DE number 2086903 (Why is no real title available?)
- scientific article; zbMATH DE number 3801619 (Why is no real title available?)
- scientific article; zbMATH DE number 1842494 (Why is no real title available?)
- scientific article; zbMATH DE number 799769 (Why is no real title available?)
- scientific article; zbMATH DE number 3221502 (Why is no real title available?)
- A general framework for subexponential discrete logarithm algorithms
- A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm
- 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
- A public key cryptosystem and a signature scheme based on discrete logarithms
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Breaking Pairing-Based Cryptosystems Using η T Pairing over GF(397)
- 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}}\))
- Complexity of a determinate algorithm for the discrete logarithm
- Computing discrete logarithms in \(\mathbb F_{3^{6 \cdot 137}}\) and \(\mathbb F_{3^{6 \cdot 163}}\) using Magma
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- Discrete logarithm in \(\mathrm{GF}(2^{809})\) with FFS
- Discrete logarithms and local units
- Discrete logarithms: The past and the future
- Efficient signature generation by smart cards
- Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
- Extended tower number field sieve: a new complexity for the medium prime case
- Factoring polynomials with rational coefficients
- Fast evaluation of logarithms in fields of characteristic two
- Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields
- Finding Isomorphisms Between Finite Fields
- Function field sieve method for discrete logarithms over finite fields
- Generators and irreducible polynomials over finite fields
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
- Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
- Monte Carlo Methods for Index Computation (mod p)
- New directions in cryptography
- On \(x^{q+1}+ax+b\)
- On a problem of Oppenheim concerning Factorisatio Numerorum
- On the discrete logarithm problem in elliptic curves
- 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}}\)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Public Key Cryptography - PKC 2006
- Solving a $$6120$$ -bit DLP on a Desktop Computer
- Solving a 676-bit discrete logarithm problem in \(\text{GF}(3^{6n})\)
- Solving sparse linear equations over finite fields
- Special prime numbers and discrete logs in finite prime fields
- The Function Field Sieve in the Medium Prime Case
- The Number Field Sieve in the Medium Prime Case
- The development of the number field sieve
- The past, evolving present, and future of the discrete logarithm
- The tower number field sieve
- Using number fields to compute logarithms in finite fields
- Virtual logarithms
- Weakness of $\mathbb{F}_{3^{6 \cdot 509}}$ for Discrete Logarithm Cryptography
- \(X^{2^l+1}+x+a\) and related affine polynomials over \(\mathrm{GF}(2^k\))
Cited in
(14)- Traps to the BGJT-algorithm for discrete logarithms
- Indiscreet discrete logarithms
- Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
- Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
- Cryptographic group and semigroup actions
- Cryptography and Coding
- 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 the discrete logarithm problem in finite fields of fixed characteristic
- Roots of certain polynomials over finite fields
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
- Computing discrete logarithms
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields
This page was built for publication: Indiscreet logarithms in finite fields of small characteristic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1783724)
