Traps to the BGJT-Algorithm for Discrete Logarithms
This addresses a critical flaw in a breakthrough algorithm for cryptography, but the fix is incremental and heuristic, requiring further validation.
The paper identifies problematic heuristics in the BGJT quasi-polynomial time algorithm for discrete logarithms in small characteristic fields, particularly for non-Kummer extensions, and proposes a fix that maintains the quasi-polynomial time complexity.
In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thom{é}, 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.