On the computation of quadratic 2-class groups
Journal de théorie des nombres de Bordeaux, Volume 8 (1996) no. 2, p. 283-313

We describe an algorithm due to Gauss, Shanks and Lagarias that, given a non-square integer D0,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 logD.

Nous décrivons un algorithme dû à Gauss, Shanks et Lagarias qui étant donné un entier D0,1 mod 4 non carré et la factorisation de D, détermine la structure du 2-sous-groupe de Sylow du groupe des classes de l’ordre quadratique de déterminant D ; la complexité de cet algorithme est en temps polynomial probabiliste en logD.

Classification:  Primary 11Y40,  11R11,  Secondary 11E16,  11E20
Keywords: quadratic 2-class groups, binary and ternary quadratic forms
@article{JTNB_1996__8_2_283_0,
     author = {Bosma, Wieb and Stevenhagen, Peter},
     title = {On the computation of quadratic $2$-class groups},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {8},
     number = {2},
     year = {1996},
     pages = {283-313},
     zbl = {0870.11080},
     mrnumber = {1438471},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_1996__8_2_283_0}
}
Bosma, Wieb; Stevenhagen, Peter. On the computation of quadratic $2$-class groups. Journal de théorie des nombres de Bordeaux, Volume 8 (1996) no. 2, pp. 283-313. http://www.numdam.org/item/JTNB_1996__8_2_283_0/

[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. | 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