Vol. 2, 2019

 Recent Volumes 2: ANTS XIII 1: ANTS X
 The Open Book Series About the Series Ethics Statement Other MSP Publications
Counting points on genus-$3$ hyperelliptic curves with explicit real multiplication

Simon Abelard, Pierrick Gaudry and Pierre-Jean Spaenlehauer

Vol. 2 (2019), No. 1, 1–19
Abstract

We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-$3$ hyperelliptic curve defined over a finite field ${\mathbb{F}}_{q}$, with explicit real multiplication by an order $ℤ\left[\eta \right]$ in a totally real cubic field. Our main result states that this algorithm requires an expected number of $\stackrel{˜}{O}\left({\left(logq\right)}^{6}\right)$ bit-operations, where the constant in the $\stackrel{˜}{O}\left(\phantom{\rule{2.77626pt}{0ex}}\right)$ depends on the ring $ℤ\left[\eta \right]$ and on the degrees of polynomials representing the endomorphism $\eta$. As a proof-of-concept, we compute the zeta function of a curve defined over a 64-bit prime field, with explicit real multiplication by $ℤ\left[2cos\left(2\pi ∕7\right)\right]$.

Keywords
point-counting, hyperelliptic curves, Schoof's algorithm, real multiplication
Mathematical Subject Classification 2010
Primary: 11G20
Secondary: 11M38, 11Y16