|
Applying sieving to the computation of quadratic class groups
Author(s):
Michael
J.
Jacobson Jr..
Journal:
Math. Comp.
68
(1999),
859-867.
MSC (1991):
Primary 11Y40;
Secondary 11Y16
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We present a new algorithm for computing the ideal class group of an imaginary quadratic order which is based on the multiple polynomial version of the quadratic sieve factoring algorithm. Although no formal analysis is given, we conjecture that our algorithm has sub-exponential complexity, and computational experience shows that it is significantly faster in practice than existing algorithms.
References:
- 1.
- C.S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany, 1994.
- 2.
- E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380. MR 91m:11096
- 3.
- -, Improved approximations for Euler products, Number Theory: CMS Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13-28. MR 96i:11124
- 4.
- I. Biehl, J. Buchmann, and T. Papanikolaou, LiDIA - a library for computational number theory, The LiDIA Group, Universität des Saarlandes, Saarbrücken, Germany, 1995.
- 5.
- J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres (Paris), 1988-89, pp. 27-41. MR 92g:11125
- 6.
- J. Buchmann and S. Düllmann, Distributed class group computation, Festschrift aus Anlaß des sechzigsten Geburtstages von Herrn Prof. Dr. G. Hotz, Universität des Saarlandes, 1991, and Teubner, Stuttgart, 1992, pp. 69-79. MR 93e:11153
- 7.
- -, A probabilistic class group and regulator algorithm and its implementation, Computational Number Theory, Walter de Gruyter & Co., New York, 1991, pp. 53-72. MR 92m:11150
- 8.
- H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. MR 94i:11105
- 9.
- H. Cohen, F. Diaz y Diaz, and M. Olivier, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel, Séminaire de Théorie des Nombres (Paris), 1993, pp. 35-46. MR 94m:11151
- 10.
- S. Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany, 1991.
- 11.
- J.L. Hafner and K.S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), 837-850. MR 91f:11090
- 12.
- M.J. Jacobson, Jr., Some experimental results on ideal class groups of quadratic fields, Unpublished MS., 1997.
- 13.
- S. Paulus, An algorithm of subexponential type computing the class group of quadratic orders over principal ideal domains, Algorithmic Number Theory (Université Bordeaux I, Talence, France), Lecture Notes in Computer Sci., vol. 1122, Springer-Verlag, Berlin, 1996, pp. 243-257. MR 98e:11143
- 14.
- M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), 757-780. MR 88d:11129
- 15.
- R.D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329-339. MR 88c:11079
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
11Y40,
11Y16
Retrieve articles in all Journals with MSC
(1991):
11Y40,
11Y16
Additional Information:
Michael
J.
Jacobson
Jr.
Affiliation:
Technische Universität Darmstadt, FB Informatik, Institut für theoretische Informatik, Alexanderstr. 10, 64283 Darmstadt, Germany
Email:
jacobs@cdc.informatik.tu-darmstadt.de
DOI:
10.1090/S0025-5718-99-01003-0
PII:
S 0025-5718(99)01003-0
Keywords:
Quadratic order,
class group,
sieving
Received by editor(s):
May 5, 1997
Received by editor(s) in revised form:
August 4, 1997
Additional Notes:
The author is supported by the Natural Sciences and Engineering Research Council of Canada
Copyright of article:
Copyright
1999,
American Mathematical Society
|
Comments: webmaster@ams.org