On the relation generation method of Joux for computing discrete logarithms
This work is incremental, as it refines existing quasi-polynomial time algorithms for computing discrete logarithms in finite fields of small characteristic by addressing specific heuristic limitations.
The paper addresses the heuristic assumptions in Joux's discrete logarithm algorithm and its descent extension, identifying obstructions that prevent these assumptions from holding generally and proposing methods to overcome them.
In \cite{joux}, 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 $\mathbb{F}_{p^n}$ in time polynomial in $p$ and $n$. Shortly after, Barbulescu, Gaudry, Joux and Thome \cite{bgjt} proposed a descent algorithm that in $(p n)^{\mathcal{O}(\log n)}$ time projects an arbitrary element in $\mathbb{F}_{p^n}^\times$ 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.