salle A. Turing CE4
18 April 2013 - 14h00
Sur le problème du logarithme discret pour les courbes elliptiques
by Claus Diem from Institute of Mathematics, University of Leipzig
Résumé : Il est bien connu que le problème du logarithme discrete classique, c'est-à-dire, le problème de calculer des logarithmes discrets dans les groupes muliplicatifs des corps finis, peut être resolu en temps sous-exponentiel avec un algorithme randomisé. Le même est valable pour le problème du logarithme discret dans les groupes multiplicatifs de tous les corps finis.
Les algorithmes correspondants s'appuient sur la méthode de calcul d'index,
qui à peu près se compose de calcul de relations et d'algèbre linéaire.
Il y a environ 25 ans, N. Koblitz et V. Miller ont proposé de considérer le problème du logarithme discret dans les courbes elliptiques sur les corps finis pour des applications cryptographiques. La motivation essentielle était que il devrait être très difficile d'appliquer avec succès la méthode de calcul d'index à ces groupes.
Dans mon exposé, je montrerai que néanmoins la méthode de calcul d'index peut être appliquée avec succès au problème du logarithme discret dans les
courbes elliptiques sur les corps finis non-premiers. J'argumenterai que pour
certains familles des corps finis, le problème du logarithme discret dans les
courbes elliptiques sur ces corps peut être resolu en temps sous-exponentiel
avec un algorithme randomisé.
Slides of the Presentation.
