Applying sieving to the computation of quadratic class groups
HTML articles powered by AMS MathViewer
- by Michael J. Jacobson Jr. PDF
- Math. Comp. 68 (1999), 859-867 Request permission
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
- 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.
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
- Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13–28. MR 1353917, DOI 10.1016/0009-2614(95)01161-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.
- Johannes 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–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
- Johannes Buchmann and Stephan Düllmann, Distributed class group computation, Informatik, Teubner-Texte Inform., vol. 1, Teubner, Stuttgart, 1992, pp. 69–79. MR 1182565, DOI 10.1007/978-3-322-95233-2_{5}
- J. Buchmann and S. Düllmann, A probabilistic class group and regulator algorithm and its implementation, Computational number theory (Debrecen, 1989) de Gruyter, Berlin, 1991, pp. 53–72. MR 1151855
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-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, 1990–91, Progr. Math., vol. 108, Birkhäuser Boston, Boston, MA, 1993, pp. 35–46 (French). MR 1263522
- 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.
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- M.J. Jacobson, Jr., Some experimental results on ideal class groups of quadratic fields, Unpublished MS., 1997.
- Nelson Dunford, A mean ergodic theorem, Duke Math. J. 5 (1939), 635–646. MR 98
- Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI 10.1090/S0025-5718-1987-0878705-X
- Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8
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
- 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 1999 American Mathematical Society
- Journal: Math. Comp. 68 (1999), 859-867
- MSC (1991): Primary 11Y40; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-99-01003-0
- MathSciNet review: 1604324