Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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.

 

Linear algebra algorithms for divisors on an algebraic curve
HTML articles powered by AMS MathViewer

by Kamal Khuri-Makdisi PDF
Math. Comp. 73 (2004), 333-357 Request permission

Abstract:

We use an embedding of the symmetric $d$th power of any algebraic curve $C$ of genus $g$ into a Grassmannian space to give algorithms for working with divisors on $C$, using only linear algebra in vector spaces of dimension $O(g)$, and matrices of size $O(g^2)\times O(g)$. When the base field $k$ is finite, or if $C$ has a rational point over $k$, these give algorithms for working on the Jacobian of $C$ that require $O(g^4)$ field operations, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to deal with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Florian Hess’ 1999 Ph.D. thesis, which works with function fields as extensions of $k[x]$. However, for special classes of curves, Hess’ algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor 1987), superelliptic curves (Galbraith, Paulus, and Smart 2002), and $C_{ab}$ curves (Harasawa and Suzuki 2000); in all those cases, one can attain a complexity of $O(g^2)$.
References
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: kmakdisi@aub.edu.lb
  • Received by editor(s): November 7, 2001
  • Received by editor(s) in revised form: March 29, 2002
  • Published electronically: July 7, 2003
  • © Copyright 2003 American Mathematical Society
  • Journal: Math. Comp. 73 (2004), 333-357
  • MSC (2000): Primary 11Y16, 14Q05, 14H40, 11G20
  • DOI: https://doi.org/10.1090/S0025-5718-03-01567-9
  • MathSciNet review: 2034126