Localisation

Adresses

Aix-Marseille Université
Institut de Mathématiques de Marseille (I2M) - UMR 7373
Site Saint-Charles : 3 place Victor Hugo, Case 19, 13331 Marseille Cedex 3
Site Luminy : Campus de Luminy - Case 907 - 13288 Marseille Cedex 9

Séminaire

Existe-t-il un algorithme de complexité L(1/4) pour calculer des logarithmes discrets dans les courbes algébriques?

Maike Massierer


Date(s) : 26/02/2015   iCal
11h00 - 12h00

La sécurité de plusieurs systèmes cryptographiques se base sur la difficulté de calculer des logarithmes discrets dans certains groupes, surtout les groupes multiplicatifs des corps finis et les jacobines des courbes algébriques. Une piste active de recherche en théorie des nombres algorithmique concerne donc l’étude des algorithmes qui calculent des logarithmes discrets.

Le crible de corps de fonctions, un algorithme de complexité sous-exponentielle L(1/3) qui calcule des logarithmes discrets dans des corps finis, a récemment été amélioré, donnant tout d’abord un algorithme de complexité L(1/4), puis un algorithme quasi-polynomial.
Les algorithmes de calcul d’indices pour calculer des logarithmes discrets dans les jacobiennes des courbes algébriques sont basés sur des idées et des résultats très similaires. On peut alors se demander si les améliorations récentes du crible de corps de fonctions s’appliquent également dans le contexte des courbes algébriques. On évoquera plusieurs idées, expériences pratiques et conclusions possibles sans pouvoir toutefois donner de réponse définitive à cette question.

Maike Massierer, UNSW Sydney

Catégories


Secured By miniOrange