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