2004/05/15 by Kirsten Eisentraeger, Kristin Lauter, Eisentraeger, Kirsten +1
Computer Science · Mathematics · #11G10 #11G15 #11R37 #14G50 #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #math.AG #math.NT #msc:11G10 #msc:11G15 #msc:11R37 #msc:14G50
paper · pdf · doi:10.48550/arxiv.math/0405305
16 pages. to appear in Proceedings of AGCT-10
openalex publication_date 2004/05/15 · arxiv created 2007/01/11 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.