Traps to the BGJT-Algorithm for Discrete Logarithms
Preprint
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Finding primitive elements in finite fields of small characteristic2015
- A New Index Calculus Algorithm with Complexity $L(1/4+o(1))$ in Small Characteristic2014
- A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic2014
- Generators and irreducible polynomials over finite fieldsMathematics of Computation, 1997
- Fast evaluation of logarithms in fields of characteristic twoIEEE Transactions on Information Theory, 1984
- New directions in cryptographyIEEE Transactions on Information Theory, 1976