Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: kmakdisi@aub.edu.lb

DOI: http://dx.doi.org/10.1090/S0025-5718-07-01989-8
PII: S 0025-5718(07)01989-8
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.