Improved CRT Algorithm for Class Polynomials in Genus 2

Date Added: Aug 2012
Format: PDF

The authors present a generalization to genus 2 of the probabilistic algorithm in Sutherland for computing Hilbert class polynomials. The improvement over the algorithm presented for the genus 2 case, is that they do not need to find a curve in the isogeny class with endomorphism ring which is the maximal order: rather they present a probabilistic algorithm for "Going Up" to a maximal curve (a curve with maximal endomorphism ring), once they find any curve in the right isogeny class. Then they 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.