Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Asymptotically fast group operations on Jacobians of general curves

Author: Kamal Khuri-Makdisi
Journal: Math. Comp. 76 (2007), 2213-2239
MSC (2000): Primary 11Y16, 14Q05, 14H40, 11G20
Published electronically: April 23, 2007
MathSciNet review: 2336292
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 14Q05, 14H40, 11G20

Retrieve articles in all journals with MSC (2000): 11Y16, 14Q05, 14H40, 11G20

Additional Information

Kamal Khuri-Makdisi
Affiliation: Mathematics Department and Center for Advanced Mathematical Sciences, American University of Beirut, Bliss Street, Beirut, Lebanon
MR Author ID: 610136

Received by editor(s): July 3, 2006
Received by editor(s) in revised form: August 20, 2006
Published electronically: April 23, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.