Traps to the BGJT-algorithm for discrete logarithms
- 1 August 2014
- journal article
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 17 (A) , 218-229
Abstract
In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thomé, a quasi-polynomial time algorithm 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 propose a fix to the algorithm in non-Kummer cases, without altering the heuristic quasi-polynomial time complexity. Further study is required in order to fully understand the effectiveness of the new approach.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Faster Index Calculus for the Medium Prime Case Application to 1175-bit and 1425-bit Finite FieldsLecture Notes in Computer Science, 2013
- A General Framework for Subexponential Discrete Logarithm Algorithms in Groups of Unknown Order2001
- An analytic approach to smooth polynomials over finite fields1998
- Generators and irreducible polynomials over finite fieldsMathematics of Computation, 1997
- The function field sieve1994
- Discrete Logarithms in $GF ( P )$ Using the Number Field SieveSIAM Journal on Discrete Mathematics, 1993
- A public key cryptosystem and a signature scheme based on discrete logarithmsIEEE Transactions on Information Theory, 1985
- Fast evaluation of logarithms in fields of characteristic twoIEEE Transactions on Information Theory, 1984
- Monte Carlo Methods for Index Computation (mod p)Mathematics of Computation, 1978
- New directions in cryptographyIEEE Transactions on Information Theory, 1976