Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Asymptotically fast group operations on Jacobians of general curves
HTML articles powered by AMS MathViewer

by Kamal Khuri-Makdisi PDF
Math. Comp. 76 (2007), 2213-2239 Request permission


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$.
Similar Articles
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
  • Email:
  • Received by editor(s): July 3, 2006
  • Received by editor(s) in revised form: August 20, 2006
  • Published electronically: April 23, 2007
  • © Copyright 2007 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 76 (2007), 2213-2239
  • MSC (2000): Primary 11Y16, 14Q05, 14H40, 11G20
  • DOI:
  • MathSciNet review: 2336292