Cryptology ePrint Archive: Report 2013/673
Traps to the BGJT-Algorithm for Discrete Logarithms
Qi Cheng and Daqing Wan and Jincheng Zhuang
Abstract: 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.
Category / Keywords: public-key cryptography / discrete logarithm problem
Date: received 20 Oct 2013
Contact author: qcheng at cs ou edu
Available format(s): PDF | BibTeX Citation
Version: 20131024:084212 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]