salle A. Turing CE4
3 juillet 2013 - 14h00
Revisiting discrete logarithms in small/medium characteristic finite fields
par Antoine Joux de Prism UVSQ
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 is a new method for generating
multiplicative relations with a systematic side by composing the
polynomial (X^q-X) with homographies.
This results in an algorithm of quasi-polynomial complexity for discrete
logs in GF(q^k) where k is close to q.
