Jeudi 10 mars 2016 à 15h00 en salle C47
Cyril Hugounenq (UVSQ)
Titre : Calcul d'isogénies en temps quadratique à l'aide de volcans d'isogénies
Résumé :
Le but de ce travail conjoint avec Luca De Feo, Jérôme Plût et Eric
Schost est de résoudre le problème suivant:
Soit E, E' deux courbes elliptiques que l'on sait r-isogènes, on veut
alors calculer la r-isogénie en un temps quadratique en r.
Couveignes [1994] avait proposé un algorithme permettant de résoudre
ce problème en temps quasi quadratique, cependant celui-ci était
exponentiel en p la caractéristique du corps sur lequel étaient
définies les courbes elliptiques. En effet Couveignes interpolait
l'isogénie en considérant les groupes cycliques de p^{k} torsion et
prenait en compte pour l'interpolation la loi de groupe.
Notre approche est de travailler avec la \ell^{k} torsion, cependant
si l'on fait cela naïvement on aura alors un trop grand nombre
d'essais d'interpolation à considérer. L'exposé va donc montrer
comment à l'aide des volcans d'isogénie résoudre ce problème à faible
coût.
Les volcans d'isogénie ont été introduit par Eric Kohel dans sa thèse
[1996], puis ont été étudié notamment par Fouquet Morain [2001] afin
de trouver des algorithmes qui permettent de décrire la structure du
volcan. Une étude sur le lien entre le volcan et la structure
algébrique de la courbe a été faite notamment par Miret, Moreno,
Sadornil, Tena, Valls [2005] ou encore Ionica Joux [2010], qui ont
amélioré dans certains cas l'algorithme de Fouquet Morain.
L'exposé va présenter dans un premier temps les volcans de \ell
iosgénie (\ell premier différent de r), le lien entre le niveau d'une
courbe dans le volcan et sa structure algébrique d'après les travaux
de Miret, Moreno, Sadornil, Tena, Valls, et Ionica Joux.
Dans un deuxième temps on va voir comment l'on peut trouver des
informations sur le volcan à l'aide de l'étude de l'action du
Frobenius sur la \ell^{\infty} torsion. On verra alors comment
considérer un ensemble restreint de points à interpoler.
Si le temps le permet l'exposé abordera comment prendre avantage des
constructions de tour 2-adique d'après le travail de Doliskani-Schost
[2015], afin de réduire le coût de l'interpolation.