Computing in the Jacobian of a hyperelliptic curve
Author:
David G. Cantor
Journal:
Math. Comp. 48 (1987), 95101
MSC:
Primary 11Y16; Secondary 11G20, 14H25, 14H40
MathSciNet review:
866101
Fulltext 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,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [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 YorkLondon, 1958. MR 0100591
(20 #7021)
 [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
(88e:11130), http://dx.doi.org/10.1090/S00255718198708661137
 [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
(86b:14017)
 [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
(85d:11106), http://dx.doi.org/10.1090/S00255718198407449395
 [8]
Martin
Seysen, A probabilistic factorization
algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705
(88d:11129), http://dx.doi.org/10.1090/S0025571819870878705X
 [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
(47 #4932)
 [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
(84m:12010), http://dx.doi.org/10.1090/S00255718198307016382
 [1]
 Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, AddisonWesley, Reading, Mass., 1974. MR 0413592 (54:1706)
 [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, New York, 1958. MR 0100591 (20:7021)
 [4]
 H. W. Lenstra, Jr., "Factorization using elliptic curves." (To be published.)
 [5]
 Peter Montgomery, "Speeding the Pollard and elliptic curve methods of factorization," Math. Comp., v. 48, 1977, pp. 243264. MR 866113 (88e:11130)
 [6]
 David Mumford, Tata Lectures on Theta II, Birkhäuser, Boston, 1984, ISBN 0817631100. MR 742776 (86b:14017)
 [7]
 C. P. Schnorr & H. W. Lenstra, Jr., "A Monte Carlo factoring algorithm with linear storage," Math. Comp., v. 43, 1984, pp. 289311. MR 744939 (85d:11106)
 [8]
 Martin Seysen, "A probabilistic factorization algorithm with quadratic forms of negative discriminant," Math. Comp. (To appear.) MR 878705 (88d:11129)
 [9]
 Daniel Shanks, Class Number, A Theory of Factorization, and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415440. MR 0316385 (47:4932)
 [10]
 H. C. Williams, G. W. Dueck & B. K. Schmid, "A rapid method of evaluating the regulator and class number of a pure cubic field," Math. Comp., v. 41, 1983, pp. 235286. MR 701638 (84m:12010)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y16,
11G20,
14H25,
14H40
Retrieve articles in all journals
with MSC:
11Y16,
11G20,
14H25,
14H40
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198708661010
PII:
S 00255718(1987)08661010
Article copyright:
© Copyright 1987
American Mathematical Society
