On the relation generation method of Joux for computing discrete logarithms

2013/12/05 by Ming-Deh A. Huang, Anand Kumar Narayanan, Huang, Ming-Deh +1
Computer Science · #Cryptography and Residue Arithmetic #Coding theory and cryptography #Cryptography and Data Security

paper · pdf · doi:10.48550/arxiv.1312.1674

Abstract

In \citejoux, Joux devised an algorithm to compute discrete logarithms between elements in a certain subset of the multiplicative group of an extension of the finite field \mathbbF_pⁿ in time polynomial in p and n. Shortly after, Barbulescu, Gaudry, Joux and Thome \citebgjt proposed a descent algorithm that in (p n)^{O(log n)} time projects an arbitrary element in \mathbbF_pⁿ^× as a product of powers of elements in the aforementioned subset. Together, these two algorithms yield a quasi-polynomial time algorithm for computing discrete logarithms in finite fields of small characteristic. The success of both the algorithms are reliant on heuristic assumptions. We identify obstructions that prevent certain heuristic assumptions they make from being true in general. Further, we describe methods to overcome these obstructions.

Related

• A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
• Discrete logarithms in quasi-polynomial time in finite fields of fixed\n characteristic
• Finding Primitive Elements in Finite Fields of Small Characteristic
• A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Computing discrete logarithms in subfields of residue class rings