Asymptotically fast group operations on Jacobians of general curves

Khuri-Makdisi, Kamal

doi:10.1090/S0025-5718-07-01989-8

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

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

Dan Abramovich, A linear lower bound on the gonality of modular curves, Internat. Math. Res. Notices 20 (1996), 1005–1011. MR 1422373, DOI 10.1155/S1073792896000621
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
Greg W. Anderson, Abeliants and their application to an elementary construction of Jacobians, Adv. Math. 172 (2002), no. 2, 169–205. MR 1942403, DOI 10.1016/S0001-8708(02)00024-5
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
Joel Brawley and Shuhong Gao, On density of primitive elements for field extensions, 2004 preprint, may be electronically downloaded from the web at the URL http://www.math.clemson.edu/~sgao/pub.html
Thomas Becker and Volker Weispfenning, Gröbner bases, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. A computational approach to commutative algebra; In cooperation with Heinz Kredel. MR 1213453, DOI 10.1007/978-1-4612-0913-3
David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95–101. MR 866101, DOI 10.1090/S0025-5718-1987-0866101-0
Wei-Liang Chow, The Jacobian variety of an algebraic curve, Amer. J. Math. 76 (1954), 453–476. MR 61421, DOI 10.2307/2372585
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
Wolfram Decker, Gert-Martin Greuel, and Gerhard Pfister, Primary decomposition: algorithms and comparisons, Algorithmic algebra and number theory (Heidelberg, 1997) Springer, Berlin, 1999, pp. 187–220. MR 1672046
W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras over finite fields, J. Symbolic Comput. 29 (2000), no. 3, 441–458. MR 1751390, DOI 10.1006/jsco.1999.0308
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, DOI 10.1002/9781118032527
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. 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_FH.ps.gz
F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
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 10.1006/jsco.1994.1063
Gregor Kemper, The calculation of radical ideals in positive characteristic, J. Symbolic Comput. 34 (2002), no. 3, 229–238. MR 1935080, DOI 10.1006/jsco.2002.0560
Kamal Khuri-Makdisi, Linear algebra algorithms for divisors on an algebraic curve, Math. Comp. 73 (2004), no. 245, 333–357. MR 2034126, DOI 10.1090/S0025-5718-03-01567-9
Kamal Khuri-Makdisi, Asymptotically fast group operations on Jacobians of general curves (previous draft, version 2), 2004 preprint, may be electronically downloaded from the web at the URL http://arxiv.org/abs/math.NT/0409209v2
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
The PARI Group, Bordeaux, PARI/GP, may be downloaded from the web at the URL http://pari.math.u-bordeaux.fr/
W. Stein, Modular Forms Database, http://modular.math.washington.edu/Tables
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 10.1007/3-540-58691-1_{6}0