We propose a Las Vegas probabilistic algorithm to compute the zeta function of a
genus-
hyperelliptic curve defined over a finite field
, 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
bit-operations, where
the constant in the
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
.
Keywords
point-counting, hyperelliptic curves, Schoof's algorithm,
real multiplication