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

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.