On the computation of quadratic $2$-class groups

Wieb Bosma; Peter Stevenhagen

On the computation of quadratic

2

-class groups

Wieb Bosma ; Peter Stevenhagen

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”

Résumé
Abstract

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

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 |D|$ .

MR Zbl

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 = {Wieb Bosma and Peter Stevenhagen},
     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},
     zbl = {0870.11080},
     mrnumber = {1438471},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_283_0/}
}

TY  - JOUR
AU  - Wieb Bosma
AU  - Peter Stevenhagen
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  - https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_283_0/
LA  - en
ID  - JTNB_1996__8_2_283_0
ER  -

%0 Journal Article
%A Wieb Bosma
%A Peter Stevenhagen
%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 https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_283_0/
%G en
%F JTNB_1996__8_2_283_0

Wieb Bosma; Peter Stevenhagen. On the computation of quadratic $2$-class groups. Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 283-313. https://jtnb.centre-mersenne.org/item/JTNB_1996__8_2_283_0/

Bibliographie
Cité par

[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