Discrete logarithms in small characteristic finite fields: A L(1/4+o(1)) algorithm

Antoine Joux


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)).

Time and Place

Wednesday, June 5, 2013, 4pm
Gates 463A