A p-adic quasi-quadratic point counting algorithm
| dc.creator | Carls, Robert | |
| dc.creator | Lubicz, David | |
| dc.date | 2007-06-01 | |
| dc.date | 2008-06-27 | |
| dc.date.accessioned | 2026-07-07T09:46:45Z | |
| dc.date.available | 2026-07-07T09:46:45Z | |
| dc.description | In this article we give an algorithm for the computation of the number of rational points on the Jacobian variety of a generic ordinary hyperelliptic curve defined over a finite field of cardinality $q$ with time complexity $O(n^{2+o(1)})$ and space complexity $O(n^2)$, where $n=\log(q)$. In the latter complexity estimate the genus and the characteristic are assumed as fixed. Our algorithm forms a generalization of both, the AGM algorithm of J.-F. Mestre and the canonical lifting method of T. Satoh. We canonically lift a certain arithmetic invariant of the Jacobian of the hyperelliptic curve in terms of theta constants. The theta null values are computed with respect to a semi-canonical theta structure of level $2^νp$ where $ν>0$ is an integer and $p=\mathrm{char}(\F_q)>2$. The results of this paper suggest a global positive answer to the question whether there exists a quasi-quadratic time algorithm for the computation of the number of rational points on a generic ordinary abelian variety defined over a finite field. | |
| dc.description | 32 pages | |
| dc.identifier | https://arxiv.org/abs/0706.0234 | |
| dc.identifier | http://arxiv.org/abs/0706.0234 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163636 | |
| dc.subject | Number Theory | |
| dc.subject | Algebraic Geometry | |
| dc.subject | 11G10, 11G20 | |
| dc.title | A p-adic quasi-quadratic point counting algorithm | |
| dc.type | text |