Asymptotically fast group operations on Jacobians of general curves
| dc.creator | Khuri-Makdisi, Kamal | |
| dc.date | 2004-09-13 | |
| dc.date | 2006-07-02 | |
| dc.date.accessioned | 2026-07-07T08:24:48Z | |
| dc.date.available | 2026-07-07T08:24:48Z | |
| dc.description | Let $C$ be a curve of genus $g$ over a field $k$. We describe probabilistic algorithms for addition and inversion of the classes of rational divisors in the Jacobian of $C$. After a precomputation, which is done only once for the curve $C$, the algorithms use only linear algebra in vector spaces of dimension at most $O(g \log g)$, and so take $O(g^{3 + ε})$ field operations in $k$, using Gaussian elimination. Using fast algorithms for the linear algebra, one can improve this time to $O(g^{2.376})$. This represents a significant improvement over the previous record of $O(g^4)$ field operations (also after a precomputation) for general curves of genus $g$. | |
| dc.description | 27 pages, considerably improved and streamlined revision of previous draft. Readers wishing to consult the previous extended draft should download version 2 of this paper | |
| dc.identifier | https://arxiv.org/abs/math/0409209 | |
| dc.identifier | http://arxiv.org/abs/math/0409209 | |
| dc.identifier | Math. Comp. 76 (2007), 2213-2239 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/136465 | |
| dc.subject | Number Theory | |
| dc.subject | Algebraic Geometry | |
| dc.subject | 11Y16, 14Q05, 14H40, 11G20 | |
| dc.title | Asymptotically fast group operations on Jacobians of general curves | |
| dc.type | text |