# Improved CRT Algorithm for Class Polynomials in Genus $2$

1 Cryptography group
Microsoft Research [Redmond]
2 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We present a generalization to genus~2 of the probabilistic algorithm of Sutherland for computing Hilbert class polynomials. The improvement over the Br{ö}ker-Gruenewald-Lauter algorithm for the genus~2 case is that we do not need to find a curve in the isogeny class whose endomorphism ring 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 $(\ell,\ell)$-isogenies to compute all isogenous maximal curves from an initial one. This is an extended version of the article published at ANTS~X.
Keywords :
Document type :
Conference papers

Cited literature [33 references]

https://hal.archives-ouvertes.fr/hal-00734450
Contributor : Damien Robert Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2013 - 9:51:07 AM
Last modification on : Saturday, December 4, 2021 - 3:42:11 AM
Long-term archiving on: : Monday, April 3, 2017 - 6:23:57 AM

### File

writeuplong.pdf
Files produced by the author(s)

### Citation

Kristin Lauter, Damien Robert. Improved CRT Algorithm for Class Polynomials in Genus $2$. ANTS X - Algorithmic Number Theory 2012, Jul 2012, San Diego, United States. pp.437-461, ⟨10.2140/obs.2013.1.437⟩. ⟨hal-00734450v2⟩

### Metrics

Les métriques sont temporairement indisponibles