A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
This provides a significant theoretical advancement for cryptography, as it breaks the security of certain cryptosystems based on discrete logarithms in small characteristic fields, though it is incremental in building on recent works by Joux.
The paper tackles the discrete logarithm problem in finite fields of small characteristic by developing a new algorithm with a quasi-polynomial heuristic complexity of n^{O(log n)}, which is a major asymptotic improvement over previous L(1/4+o(1)) complexities.
In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type $n^{O(\log n)}$ where $n$ is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any $L(\varepsilon)$ for $ε>0$. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to $L(1/4+o(1))$.