A point counting algorithm using cohomology with compact support
| dc.creator | Chatel, Gweltaz | |
| dc.creator | Lubicz, David | |
| dc.date | 2008-05-30 | |
| dc.date.accessioned | 2026-07-07T09:41:51Z | |
| dc.date.available | 2026-07-07T09:41:51Z | |
| dc.description | 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. | |
| dc.description | 32 pages | |
| dc.identifier | https://arxiv.org/abs/0805.4689 | |
| dc.identifier | http://arxiv.org/abs/0805.4689 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161975 | |
| dc.subject | Algebraic Geometry | |
| dc.subject | 14Q05 | |
| dc.title | A point counting algorithm using cohomology with compact support | |
| dc.type | text |