On the computation of quadratic 2-class groups
Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 283-313.
corrigé par Erratum “On the computation of quadratic 2-class groups”

Nous décrivons un algorithme dû à Gauss, Shanks et Lagarias qui étant donné un entier D≡0,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.

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

Classification : Primary 11Y40, 11R11, Secondary 11E16, 11E20
Mots-clés : 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},
     pages = {283--313},
     publisher = {Universit\'e Bordeaux I},
     volume = {8},
     number = {2},
     year = {1996},
     mrnumber = {1438471},
     zbl = {0870.11080},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_1996__8_2_283_0/}
}
TY  - JOUR
AU  - Bosma, Wieb
AU  - Stevenhagen, Peter
TI  - On the computation of quadratic $2$-class groups
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1996
SP  - 283
EP  - 313
VL  - 8
IS  - 2
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_1996__8_2_283_0/
LA  - en
ID  - JTNB_1996__8_2_283_0
ER  - 
%0 Journal Article
%A Bosma, Wieb
%A Stevenhagen, Peter
%T On the computation of quadratic $2$-class groups
%J Journal de théorie des nombres de Bordeaux
%D 1996
%P 283-313
%V 8
%N 2
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_1996__8_2_283_0/
%G en
%F 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, Tome 8 (1996) no. 2, pp. 283-313. http://archive.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

W. Bosma and P. Stevenhagen, Density computations for real quadratic units, Math. Comp. 65 (1996), no. 215, 1327-1337. | MR | Zbl

[2] H. Cohen, A course in computational algebraic number theory, Springer GTM 138, 1993. | MR | Zbl

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

[4] D.A. Cox, Primes of the form x2 + ny2, Wiley-Interscience, 1989. | MR | Zbl

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

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

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 | Zbl

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

[9] P. Stevenhagen, The number of real quadratic fields having units of negative norm, Exp. Math. 2 (1993), no. 2,121-136. | MR | Zbl

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 | Zbl