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