Vol. 1, No. 1, 2013

 Recent Volumes 1: ANTS X
 The Open Book Series About the Series Ethics Statement
Improved CRT algorithm for class polynomials in genus $2$

Kristin E. Lauter and Damien Robert

Vol. 1 (2013), No. 1, 437–461
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 $\left(\ell ,\ell \right)$-isogenies to compute all isogenous maximal curves from an initial one.

Keywords
class field polynomials, CRT, hyperelliptic curve cryptography, isogenies
Mathematical Subject Classification 2010
Primary: 14K22
Secondary: 11Y40, 11Y16, 11G15, 14K02
Milestones
Published: 14 November 2013
Authors
 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 France