Discrete logarithms in small characteristic finite fields: A L(1/4+o(1)) algorithm
Antoine Joux
Abstract:
In this talk, we present a new algorithm for the computation of discrete logarithms in finite fields of small characteristic. This algorithm combines several previously existing techniques with a few additional ingredients. Among those, the most notable are:
1- A new method for generating multiplicative relations with a
"systematic side" by composing the polynomial (X^q-X) with
homographies.
2- A new descent technique that relies on the use of
Gröbner bases to solve bi-linear systems of equations.
This results in an algorithm of complexity L(1/4+o(1)) for discrete logs in GF(q^k) where k is close to q and the characteristic p is small (namely p < sqrt(q)).