A point counting algorithm using cohomology with compact support

Abstract: We describe an algorithm to count the number of rational points of an hyperelliptic curve defined over a finite field of odd characteristic which is based upon the computation of the action of the Frobenius morphism on a basis of the Monsky–Washnitzer cohomology with compact support. This algorithm follows the vein of a systematic exploration of potential applications of cohomology theories to point counting.

Our algorithm decomposes in two steps. A first step which consists of the computation of a basis of the cohomology and then a second step to obtain a representation of the Frobenius morphism. We achieve a \tilde O(g⁴n³) time complexity and O(g³ n³) memory complexity where g is the genus of the curve and n is the absolute degree of its base field. We give a detailed complexity analysis of the algorithm as well as a proof of correctness.