staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
Wieb Bosma; Peter Stevenhagen
On the computation of quadratic $2$-class groups
Journal de théorie des nombres de Bordeaux, 8 no. 2 (1996), p. 283-313, doi: 10.5802/jtnb.170
Article PDF | Reviews MR 1438471 | Zbl 0870.11080 | 1 citation in Cedram
See also an erratum to this article
Keywords: quadratic 2-class groups, binary and ternary quadratic forms

Résumé - Abstract

We describe an algorithm due to Gauss, Shanks and Lagarias that, given a non-square integer $D \equiv 0,1$ mod $4$ and the factorization of $D$, computes the structure of the $2$-Sylow subgroup of the class group of the quadratic order of discriminant $D$ in random polynomial time in $\log \left| D \right|$.

Bibliography

[1] W. Bosma, J.J. Cannon, C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput. (to appear).  Zbl 0898.68039
W. Bosma and P. Stevenhagen, Density computations for real quadratic units, Math. Comp. 65 (1996), no. 215, 1327-1337.  MR 1344607 |  Zbl 0859.11064
[2] H. Cohen, A course in computational algebraic number theory, Springer GTM 138, 1993.  MR 1228206 |  Zbl 0786.11071
[3] H. Cohen, F. Diaz y Diaz, 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, Birkhäuser, 1993, pp. 35-46.  MR 1263522 |  Zbl 0822.11086
[4] D.A. Cox, Primes of the form x2 + ny2, Wiley-Interscience, 1989.  MR 1028322 |  Zbl 0701.11001
[5] S. Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Dissertation, Universität des Saarlandes, Saarbrücken, 1991.
[6] C.F. Gauss, Disquisitiones Arithmeticae, Gerhard Fleischer, Leipzig, 1801.
[7] J. Hafner, K. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837-850.  MR 1002631 |  Zbl 0702.11088
[8] J.C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. of Algorithms 1 (1980),142-186.  MR 604862 |  Zbl 0473.68030
J.C. Lagarias, On the computational complexity of determining the solvability or un-solvability of the equation X2 - DY2 = -1, Trans. Amer. Math. Soc. 260 (1980), no. 2, 485-508.  MR 574794 |  Zbl 0446.10014
D. Shanks, Gauss's ternary form reduction and the 2-Sylow subgroup, Math. Comp. 25 (1971), no. 116, 837-853Erratum: Math. Comp. 32 (1978), 1328-1329.  MR 491495
[9] P. Stevenhagen, The number of real quadratic fields having units of negative norm, Exp. Math. 2 (1993), no. 2,121-136. Article |  MR 1259426 |  Zbl 0792.11041
P. Stevenhagen, A density conjecture for the negative Pell equation, Computational Algebra and Number Theory, Sydney 1992, Kluwer Academic Publishers, 1995, pp. 187-200.  MR 1344930 |  Zbl 0838.11066