Computing in the Jacobian of a hyperelliptic curve

Cantor, David G.

doi:10.1090/S0025-5718-1987-0866101-0

Computing in the Jacobian of a hyperelliptic curve

Author: David G. Cantor
Journal: Math. Comp. 48 (1987), 95-101
MSC: Primary 11Y16; Secondary 11G20, 14H25, 14H40
DOI: https://doi.org/10.1090/S0025-5718-1987-0866101-0
MathSciNet review: 866101
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we present algorithms, suitable for computer use, for computation in the Jacobian of a hyperelliptic curve. We present a reduction algorithm which is asymptotically faster than that of Gauss when the genus g is very large.

[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
[2] D. V. Chudnovsky & G. V. Chudnovsky, Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests, Research report RC 11262 (#50739), IBM Thomas J. Watson Research Center, Yorktown Heights, N. Y., 1985.
[3] Serge Lang, Introduction to algebraic geometry, Interscience Publishers, Inc., New York-London, 1958. MR 0100591
[4] H. W. Lenstra, Jr., "Factorization using elliptic curves." (To be published.)
[5] Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, https://doi.org/10.1090/S0025-5718-1987-0866113-7
[6] David Mumford, Tata lectures on theta. II, Progress in Mathematics, vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776
[7] C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, https://doi.org/10.1090/S0025-5718-1984-0744939-5
[8] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, https://doi.org/10.1090/S0025-5718-1987-0878705-X
[9] Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
[10] H. C. Williams, G. W. Dueck, and B. K. Schmid, A rapid method of evaluating the regulator and class number of a pure cubic field, Math. Comp. 41 (1983), no. 163, 235–286. MR 701638, https://doi.org/10.1090/S0025-5718-1983-0701638-2