1. Genus-2 curves and Jacobians with a given number of points
- Author
-
Kristin E. Lauter, Peter Stevenhagen, Reinier Bröker, and Everett W. Howe
- Subjects
Pure mathematics ,Mathematics - Number Theory ,General Mathematics ,Primary 14K22, Secondary 11G15, 11G20, 14G15 ,Prime (order theory) ,Exponential function ,Mathematics - Algebraic Geometry ,Elliptic curve ,symbols.namesake ,Mathematics::Algebraic Geometry ,Finite field ,Computational Theory and Mathematics ,Genus (mathematics) ,Jacobian matrix and determinant ,FOS: Mathematics ,symbols ,Number Theory (math.NT) ,Algebraic Geometry (math.AG) ,Parametrization ,Time complexity ,Mathematics - Abstract
We study the problem of efficiently constructing a curve C of genus 2 over a finite field F for which either the curve C itself or its Jacobian has a prescribed number N of F-rational points. In the case of the Jacobian, we show that any `CM-construction' to produce the required genus-2 curves necessarily takes time exponential in the size of its input. On the other hand, we provide an algorithm for producing a genus-2 curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-2 curve having exactly 10^2014 + 9703 (prime) points, and two genus-2 curves each having exactly 10^2013 points. In an appendix we provide a complete parametrization, over an arbitrary base field k of characteristic neither 2 nor 3, of the family of genus-2 curves over k that have k-rational degree-3 maps to elliptic curves, including formulas for the genus-2 curves, the associated elliptic curves, and the degree-3 maps., Comment: Made a number of clarifications and corrected some typographical errors
- Published
- 2015