The ants mascot

Tenth Algorithmic Number Theory Symposium ANTS-X
University of California, San Diego
July 9 – 13, 2012

Tenth Algorithmic Number Theory Symposium (ANTS-X)
July 9 – 13, 2012

Improved CRT Algorithm for class polynomials in genus 2

Kristin Lauter and Damien Robert

Abstract: We present a generalization to genus 2 of the probabilistic algorithm in Sutherland for computing Hilbert class polynomials. The improvement over the algorithm presented in [BGL] for the genus 2 case, is that we do not need to find a curve in the isogeny class with endomorphism ring which is the maximal order: rather we present a probabilistic algorithm for ``going up'' to a maximal curve (a curve with maximal endomorphism ring), once we find any curve in the right isogeny class. Then we use the structure of the Shimura class group and the computation of (l,l)-isogenies to compute all isogenous maximal curves from an initial one.

Files available: paper (PDF), slides

© 2011-12 Kiran S. Kedlaya (with thanks to Pierrick Gaudry and Emmanuel Thomé)
XHTML 1.1 valid, CSS valid