Calcul du logarithme discret dans GF(2n), en utilisant la double large prime variation.


Emmanuel THOME (LIX, Ecole Polytechnique)


Le calcul du logarithme discret dans les corps finis tels que GF(2n) est un problème difficile. Son importance en cryptographie est notamment grandie par le fait que dans certains cas, le logarithme discret sur une courbe elliptique se réduit au calcul sur un corps fini. On expliquera ici l'algorithme de Coppersmith qui calcule le logarithme discret sur GF(2n) en temps O(exp(n1/3log(n)2/3)), ainsi que la double large prime variation et ses incidences théoriques et pratiques.