Fast heuristic algorithms for computing relations in the class group of a quadratic order with applications to isogeny evaluation

Carte non disponible

Date/heure
Date(s) - 08/09/2016
11 h 00 min - 12 h 00 min

Catégories Pas de Catégories


We present novels algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. We obtain improved heuristic complexity results in almost all cases for these problems, and significantly improved performance in practice, especially in situations where the ideal class group can be computed in advance. This is joint work with C. Fieker and M. Jacobson.

http://www.lix.polytechnique.fr/Labo/Jean-Francois.Biasse/


Retour en haut 

Secured By miniOrange