Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

Counting points on genus-3 hyperelliptic curves with explicit real multiplication

Simon Abelard, Pierrick Gaudry and Pierre-Jean Spaenlehauer

Abstract: We propose a Las Vegas probabilistic algorithm to compute the zeta function of a genus-3 hyperelliptic curve defined over a finite field F_q, with explicit real multiplication by an order Z[η] in a totally real cubic field. Our main result states that this algorithm requires an expected number of Õ((log q)⁶) bit-operations, where the constant in the Õ() depends on the ring Z[η] 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 Z[2 cos(2π/7)].

Published Paper
Talk Slides