Traps to the BGJT-algorithm for discrete logarithms
From MaRDI portal
Abstract: In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thom{'e}, a quasi-polynomial time algorithm (QPA) is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular, when the field is not a Kummer extension. We believe that the basic idea behind the new approach should still work, and propose a fix to the algorithm in non-Kummer cases, without altering the quasi-polynomial time complexity. The modified algorithm is also heuristic. Further study is required in order to fully understand the effectiveness of the new approach.
Recommendations
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- Factor base discrete logarithms in Kummer extensions
- Indiscreet logarithms in finite fields of small characteristic
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- On the discrete logarithm problem in finite fields of fixed characteristic
Cites work
- A public key cryptosystem and a signature scheme based on discrete logarithms
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- 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
- Generators and irreducible polynomials over finite fields
- New directions in cryptography
- 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}}\)
- The Function Field Sieve in the Medium Prime Case
- The Number Field Sieve in the Medium Prime Case
Cited in
(5)- Factor base discrete logarithms in Kummer extensions
- Classifying and generating exact coset representatives of \(\operatorname{PGL}_2(\mathbb{F}_q)\) in \(\operatorname{PGL}_2(\mathbb{F}_{q^2})\)
- On the discrete logarithm problem in finite fields of fixed characteristic
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
This page was built for publication: Traps to the BGJT-algorithm for discrete logarithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878837)
