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

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 jacobiennes 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 au 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.