Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
The Open Book Series
About the Series
Ethics Statement
Other MSP Publications
Improved CRT algorithm for class polynomials in genus $2$

Kristin E. Lauter and Damien Robert

Vol. 1 (2013), No. 1, 437–461

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 (,)-isogenies to compute all isogenous maximal curves from an initial one.

class field polynomials, CRT, hyperelliptic curve cryptography, isogenies
Mathematical Subject Classification 2010
Primary: 14K22
Secondary: 11Y40, 11Y16, 11G15, 14K02
Published: 14 November 2013
Kristin E. Lauter
Cryptography Research Group
Microsoft Research
One Microsoft Way
Redmond, WA 98052
United States
Damien Robert
Microsoft Research
One Microsoft Way
Redmond, WA 98052
United States
INRIA Bordeaux Sud-Ouest
200 avenue de la Vieille Tour
33405 Talence cedex