Vol. 2, 2019

Download this article
Download this article For screen
For printing
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 Fq, with explicit real multiplication by an order [η] in a totally real cubic field. Our main result states that this algorithm requires an expected number of O˜((logq)6) bit-operations, where the constant in the O˜() depends on the ring [η] and on the degrees of polynomials representing the endomorphism η. 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 [2cos(2π7)].

Keywords
point-counting, hyperelliptic curves, Schoof's algorithm, real multiplication
Mathematical Subject Classification 2010
Primary: 11G20
Secondary: 11M38, 11Y16
Milestones
Received: 27 February 2018
Revised: 18 September 2018
Accepted: 18 September 2018
Published: 13 February 2019
Authors
Simon Abelard
Université de Lorraine, CNRS, Inria
Nancy
France
Pierrick Gaudry
Université de Lorraine, CNRS, Inria
Nancy
France
Pierre-Jean Spaenlehauer
Université de Lorraine, CNRS, Inria
Nancy
France