A Quasi Quadratic Time
Algorithm for Hyperelliptic Curve Point Counting.
The Ramanujan Journal, 12(3):399-423, December 2006..
We describe an algorithm to compute the cardinality of
Jacobians of ordinary hyperelliptic curves of small genus
over finite fields GF(2n) with cost O(n2+o(1)). This
algorithm is derived from ideas due to Mestre. More
precisely, we state the mathematical background behind
Mestre's al*gorithm and develop from it a variant with
quasi-quadratic time complexity. Among others, we present an
algorithm to find roots of a system of generalized
Artin-Schreier equations and give results that we obtain
with an efficient implementation. Especially, we were able
to obtain the cardinality of curves of genus one, two or
three in finite fields of huge size.
[ bib |