A CRT algorithm for constructing genus 2 curves over finite fields

Abstract

We present a new method for constructing genus 2 curves over a finite field with a given number of points on its Jacobian. This method has important applications in cryptography, where groups of prime order are used as the basis for discrete-log based cryptosystems. Our algorithm provides an alternative to the traditional CM method for constructing genus 2 curves. For a quartic CM field K with primitive CM type, we compute the Igusa class polynomials modulo p for certain small primes p and then use the Chinese remainder theorem (CRT) and a bound on the denominators to construct the class polynomials. We also provide an algorithm for determining endomorphism rings of ordinary Jacobians of genus 2 curves over finite fields, generalizing the work of Kohel for elliptic curves.

16 pages. to appear in Proceedings of AGCT-10

References in corpus (2)

• The $p$-adic CM-method for genus 2
• Computing endomorphism rings of Jacobians of genus 2 curves over finite fields

Cited by in corpus (7)

• Computing Igusa class polynomials
• Examples of CM curves of genus two defined over the reflex field
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• Pairing-based algorithms for jacobians of genus 2 curves with maximal endomorphism ring
• A CM construction for curves of genus 2 with p-rank 1
• Tame Galois realizations of GSp_4(F_l) over Q
• Spanning the isogeny class of a power of an ordinary elliptic curve over a finite field. Application to the number of rational points of curves of genus $\le 4$