Paper 2012/443

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 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.

Note: Add acknowledgements

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Published at ANTS X
Keywords
Class polynomialsgenus 2CRT
Contact author(s)
damien robert @ inria fr
History
2013-05-07: last of 3 revisions
2012-08-06: received
See all versions
Short URL
https://ia.cr/2012/443
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/443,
      author = {Kristin Lauter and Damien Robert},
      title = {Improved CRT Algorithm for Class Polynomials in Genus 2},
      howpublished = {Cryptology ePrint Archive, Paper 2012/443},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/443}},
      url = {https://eprint.iacr.org/2012/443}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.