Asymptotically fast group operations on Jacobians of general curves

Abstract

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+\epsilon })$ 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$.

arXiv comment27 pages, considerably improved and streamlined revision of previous draft. Readers wishing to consult the previous extended draft should download version 2 of this paper