Linear algebra algorithms for divisors on an algebraic curve

Author:
Kamal Khuri-Makdisi

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

Published electronically:
July 7, 2003

MathSciNet review:
2034126

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

- E. Arbarello, M. Cornalba, P. A. Griffiths, and J. Harris,
*Geometry of algebraic curves. Vol. I*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 267, Springer-Verlag, New York, 1985. MR**770932** - Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang,
*A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 28–40. MR**1322708**, DOI https://doi.org/10.1007/3-540-58691-1_39 - Siegfried Bosch, Werner Lütkebohmert, and Michel Raynaud,
*Néron models*, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 21, Springer-Verlag, Berlin, 1990. MR**1045822** - David G. Cantor,
*Computing in the Jacobian of a hyperelliptic curve*, Math. Comp.**48**(1987), no. 177, 95–101. MR**866101**, DOI https://doi.org/10.1090/S0025-5718-1987-0866101-0 - Phillip Griffiths and Joseph Harris,
*Principles of algebraic geometry*, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1994. Reprint of the 1978 original. MR**1288523** - S. D. Galbraith, S. M. Paulus, and N. P. Smart,
*Arithmetic on superelliptic curves*, Math. Comp.**71**(2002), no. 237, 393–405. MR**1863009**, DOI https://doi.org/10.1090/S0025-5718-00-01297-7 - Robin Hartshorne,
*Algebraic geometry*, Springer-Verlag, New York-Heidelberg, 1977. Graduate Texts in Mathematics, No. 52. MR**0463157** - Florian Hess,
*Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern*, Ph.D. thesis, Technische Universität Berlin, 1999, may be downloaded from the web at http://www.math.tu-berlin.de/~kant/publications/diss/diss_{F}H.ps.gz. - Florian Hess,
*Computing Riemann-Roch spaces in algebraic function fields and related topics*, J. Symbolic Comput.**33**(2002), no. 4, 425–445. - Ming-Deh Huang and Doug Ierardi,
*Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve*, J. Symbolic Comput.**18**(1994), no. 6, 519–539. MR**1334660**, DOI https://doi.org/10.1006/jsco.1994.1063 - Ryuichi Harasawa and Joe Suzuki,
*Fast Jacobian group arithmetic on $C_{ab}$ curves*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 359–376. MR**1850617**, DOI https://doi.org/10.1007/10722028_21 - Robert Lazarsfeld,
*A sampling of vector bundle techniques in the study of linear series*, Lectures on Riemann surfaces (Trieste, 1987) World Sci. Publ., Teaneck, NJ, 1989, pp. 500–559. MR**1082360** - Gary Cornell and Joseph H. Silverman (eds.),
*Arithmetic geometry*, Springer-Verlag, New York, 1986. Papers from the conference held at the University of Connecticut, Storrs, Connecticut, July 30–August 10, 1984. MR**861969** - Emil J. Volcheck,
*Computing in the Jacobian of a plane algebraic curve*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221–233. MR**1322725**, DOI https://doi.org/10.1007/3-540-58691-1_60

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

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

Article copyright:
© Copyright 2003
American Mathematical Society