Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin

Abstract:  The hardness of computing discrete logarithms in finite field has served as a foundation for many public key cryptosystems. In the last two years, tremendous progress have been made in the case of small characteristic finite fields.

In this talk, we present a simplified description of the algorithmic framework that has been developed to solve this problem faster.
This framework is an index calculus approach that relies on two main ingredients, the definition of the extension field and the generation of multiplicative relations in this field. Given a base field GF(q), we construct its extension field GF(q^k) in the following way: we find two polynomials of low degree h0 and h1 with coefficients in GF(q) such that x^q h1(x)-h0(x) has an irreducible factor of
degree k over GF(q).

To generate relations, we start from the well-known identity:
X^q-X=Prod_(c in GF(q)) X-c.

Combining substitution of X by a fraction in the identity with the field definition, we easily obtain many multiplicative relations. This is enough to obtain the logarithms of a factor base of small degree elements in polynomial time.
Once this is done, we use a descent procedure to recursively express any element of the finite field GF(q) into elements represented by polynomials of lower degree. This procedure is quite complex but ultimately leads to a quasi-polynomial time algorithm for the discrete logarithm problem in small characteristic finite fields.