On the computation of quadratic 2 -class groups

Wieb Bosma; Peter Stevenhagen

Journal de théorie des nombres de Bordeaux (1996)

  • Volume: 8, Issue: 2, page 283-313
  • ISSN: 1246-7405

Abstract

top
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 log D .

How to cite

top

Bosma, Wieb, and Stevenhagen, Peter. "On the computation of quadratic $2$-class groups." Journal de théorie des nombres de Bordeaux 8.2 (1996): 283-313. <http://eudml.org/doc/247816>.

@article{Bosma1996,
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|$.},
author = {Bosma, Wieb, Stevenhagen, Peter},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {quadratic 2-class groups; binary and ternary quadratic forms; computation; ternary quadratic forms; 2-class group; ambiguous binary forms},
language = {eng},
number = {2},
pages = {283-313},
publisher = {Université Bordeaux I},
title = {On the computation of quadratic $2$-class groups},
url = {http://eudml.org/doc/247816},
volume = {8},
year = {1996},
}

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
PB - Université Bordeaux I
VL - 8
IS - 2
SP - 283
EP - 313
AB - 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|$.
LA - eng
KW - quadratic 2-class groups; binary and ternary quadratic forms; computation; ternary quadratic forms; 2-class group; ambiguous binary forms
UR - http://eudml.org/doc/247816
ER -

References

top
  1. [1] W. Bosma, J.J. Cannon, C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput. (to appear). Zbl0898.68039
  2. W. Bosma and P. Stevenhagen, Density computations for real quadratic units, Math. Comp.65 (1996), no. 215, 1327-1337. Zbl0859.11064MR1344607
  3. [2] H. Cohen, A course in computational algebraic number theory, Springer GTM138, 1993. Zbl0786.11071MR1228206
  4. [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. Zbl0822.11086MR1263522
  5. [4] D.A. Cox, Primes of the form x2 + ny2, Wiley-Interscience, 1989. Zbl0701.11001MR1028322
  6. [5] S. Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Dissertation, Universität des Saarlandes, Saarbrücken, 1991. 
  7. [6] C.F. Gauss, Disquisitiones Arithmeticae, Gerhard Fleischer, Leipzig, 1801. 
  8. [7] J. Hafner, K. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc.2 (1989), no. 4, 837-850. Zbl0702.11088MR1002631
  9. [8] J.C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. of Algorithms1 (1980),142-186. Zbl0473.68030MR604862
  10. 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. Zbl0446.10014MR574794
  11. 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. Zbl0227.12002MR491495
  12. [9] P. Stevenhagen, The number of real quadratic fields having units of negative norm, Exp. Math.2 (1993), no. 2,121-136. Zbl0792.11041MR1259426
  13. P. Stevenhagen, A density conjecture for the negative Pell equation, ComputationalAlgebra and Number Theory, Sydney1992, Kluwer Academic Publishers, 1995, pp. 187-200. Zbl0838.11066MR1344930

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.