Utilisation des symétries pour la résolution du problème de

Récemment Diem et Gaudry ont introduit indépendemment une méthode de résolution du DLP sur les courbes elliptiques définies sur un corps fini non premier K, de degré d'extension n > 1 sur le corps de base k. Cet algorithme repose sur le principe général du calcul d'indice. Une étape cruciale de cet algorithme nécessite de décomposer des points de la courbe E(K) selon une base de facteurs. C'est à dire, étant donné un point fixé R de E(K) trouver n points Pi, 0 < i < n+1, de la base de facteurs F (sous ensemble fixé de E(K)) tels que R = P1 + ... + Pn. Une méthode de résolution algébrique de ce problème consiste à modéliser cette somme sous forme d'un système polynomial et de le résoudre. À cette fin, Semaev introduit les polynômes de sommation qui projettent le problème de décomposition de points sur l'axe des abscisses. L'application d'une restriction de Weil de K à k sur un tel polynôme de sommation engendre un système à coefficients dans k à n équations et n inconnues, dont la résolution est équivalente à celle du problème de décomposition de point. Le coût de la résolution de ces systèmes est exponentiel en n et elle devient rapidement impossible. Il est donc nécessaire d'optimiser la résolution de ces systèmes. Un moyen est d'utiliser les symétries du problème de décomposition de points. Une symétrie naturelle de ce problème, lié à la commutativité de la loi de groupe sur les points de la courbe, est l'action du groupe symétrique Sn. Dans cet exposé, nous mettrons en évidence des symétries supplémentaires. Nous étudierons en particulier deux représentations de courbes -- les courbes d'Edwards et les intersections de Jacobi -- pour lesquelles ces nouvelles symétries se propagent sur les polynômes de sommation. Pour ces représentations, nous verrons également comment elles permettent de simplifier les systèmes polynomiaux à résoudre. Finalement nous présenterons quelques résultats pratiques montrant le gain apporté par l'utilisation des symétries.