Calcul d'indice sur courbes elliptiques et résolution des systèmes polynomiaux structurés : algorithme et complexité

par Louise Huot (Université de Paris 6 - LIP6)

jeudi 28 mars 2013, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

Dans cette exposé, nous nous intéressons à la complexité de la résolution des systèmes polynomiaux structurés dans le cadre de la résolution du logarithme discret sur courbes elliptiques par calcul d'indice. La complexité de la résolution des systèmes polynomiaux reposent fortement sur celle de deux algorithmes : l'algorithme pour le calcul de bases de Gröbner, par exemple $F_5$, et l'algorithme de changement d'ordre, classiquement FGLM. L'étape bloquante de la résolution des systèmes polynomiaux est souvent le changement d'ordre. Dans le but d'améliorer la résolution de cette étape, nous présenterons un nouvel algorithme de changement d'ordre ayant une complexité polynomiale en le nombre de solutions dont l'exposant est réduit à $\omega$, la constante d'algèbre linéaire dense, au lieu de 3. De plus, pour une représentation bien choisie, Edwards ou les intersections de Jacobi, nous verrons que les systèmes polynomiaux intervenant dans le calcul d'indice possèdent des symétries nous permettant de diminuer le nombre de solutions des systèmes à résoudre. Nous verrons également, que l'utilisation des symétries fait apparaître une structure quasi-homogène qui nous permet d'accélérer aussi la première étape de la résolution, $F_5$. Finalement, pour ces représentations, la complexité de résoudre les systèmes polynomiaux intervenant dans le calcul d'indice pour une courbe elliptique définie sur $\F_{q^n}$ est réduite à $O(n^2 \cdot 2^{\omega(n-1)^2})$ en comparaison avec $O(n \cdot 2^{3n(n-1)})$ pour l'état de l'art. Travaux en collaboration avec Jean-Charles Faugère, Pierrick Gaudry et Guénaël Renault.