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

Simon Abelard (1) , Pierrick Gaudry (1) , Pierre-Jean Spaenlehauer (1)

1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms

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 Z[η] in a totally real cubic field. Our main result states that this algorithm requires an expected number of O((log q) 6) bit-operations, where the constant in the O() 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)].

Domaines: Théorie des nombres [math.NT]; Calcul formel [cs.SC]; Complexité [cs.CC]

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer. Counting points on genus-3 hyperelliptic curves with explicit real multiplication. Thirteenth Algorithmic Number Theory Symposium ANTS-XIII, Jul 2018, Madison, United States. ⟨hal-01816256v1⟩