Skip to Main content Skip to Navigation
Conference papers

Improved CRT Algorithm for Class Polynomials in Genus $2$

Kristin Lauter 1 Damien Robert 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 : Class polynomials
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

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)

Identifiers

Collections

CNRS | INRIA | ANR

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⟩

Share

Metrics

Les métriques sont temporairement indisponibles