Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-18T20:31:07.465Z Has data issue: false hasContentIssue false

Genus-2 curves and Jacobians with a given number of points

Published online by Cambridge University Press:  01 February 2015

Reinier Bröker
Affiliation:
Department of Mathematics, Brown University, Box 1917, 151 Thayer Street, Providence, RI 02912, USA email reinier@math.brown.edu
Everett W. Howe
Affiliation:
Center for Communications Research, 4320 Westerra Court, San Diego, CA 92121, USA email however@alumni.caltech.edu
Kristin E. Lauter
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA email klauter@microsoft.com
Peter Stevenhagen
Affiliation:
Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands email psh@math.leidenuniv.nl

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the problem of efficiently constructing a curve $C$ of genus  $2$ over a finite field $\mathbb{F}$ for which either the curve $C$ itself or its Jacobian has a prescribed number $N$ of $\mathbb{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 two nor three, 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.

Supplementary materials are available with this article.

Information

Type
Research Article
Copyright
© The Author(s) 2015 
Supplementary material: File

Bröker supplementary material

Bröker supplementary material 1

Download Bröker supplementary material(File)
File 16.8 KB