Mathematics – Algebraic Geometry
Scientific paper
2008-05-30
Mathematics
Algebraic Geometry
32 pages
Scientific paper
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 in 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^4 n^{3})$ worst case time complexity and $O(g^3 n^3)$ 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.
Chatel Gweltaz
Lubicz David
No associations
LandOfFree
A point counting algorithm using cohomology with compact support does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A point counting algorithm using cohomology with compact support, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A point counting algorithm using cohomology with compact support will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-317449