| Hugo Labrande |  |
 |
Date of the talk: 8 April 2015, 10h00-10h30, amphithéâtre (dans le cadre des RAIM)
Calcul de la fonction thêta de Jacobi en temps quasi-optimal
Connue et étudiée depuis plusieurs siècles par les mathématiciens, la fonction thêta de Jacobi Theta(z, tau) est une fonction à deux variables complexes ; son étude révèle un nombre remarquable de propriétés. Cette fonction intervient dans l'étude des formes modulaires, et celle des variétés algébriques complexes ; on la retrouve aussi dans certains algorithmes liés à la cryptographie sur les courbes elliptiques. Les valeurs Theta(0, tau), Theta(1/2, tau) et Theta(tau/2, tau), que l'on nomme thêta-constantes, apparaissent aussi dans une grande variété d'applications : par exemple, on peut s'en servir pour calculer le polynôme de classe de Hilbert, et ainsi générer des courbes elliptiques sûres cryptographiquement. Elles ont également des liens très forts avec la moyenne arithmético-géométrique de Gauss : c'est ce qu'utilise un algorithme de Dupont (2006) pour calculer ces valeurs à précision P bits en O(M(P) \log P) opérations sur les bits, ce qui est quasi-optimal. Nous proposons un algorithme permettant de calculer n'importe quelle valeur Theta(z, tau) à précision P avec la même complexité asymptotique quasi-optimale. Notre travail repose sur l'étude d'une certaine extension de la moyenne arithmético-géométrique ; il s'accompagne d'une implantation qui confirme les gains conséquents de cette méthode par rapport à l'état de l'art.
