On the computation of quadratic 2-class groups. (English) Zbl 0870.11080

Bosma, Wieb; Stevenhagen, Peter

J. Théor. Nombres Bordx. 8, No. 2, 283-313 (1996); erratum ibid. 9, No. 1, 249 (1997).

The authors present a detailed description of an algorithm evolved from work of Gauss, D. Shanks, and J. C. Lagarias [J. Algorithms 1, 142-186 (1980; Zbl 0473.68030)]. The idea is that the 2-class group for a discriminant \(D\) can be computed in cases where the full class group is not feasible, e.g., in random polynomial time, as long as the factors of \(D\) are known. The illustrations involve a \(D\) as a product of 5 primes close to \(10^{100}\).
The prime factors immediately give ambiguous binary forms. Forms are successively examined by residue character for identification as a square. Then such a form is represented as (say) \(k^2\) (using ternary techniques), and the desired “square-root-form” is deduced from \((k^2,l,m)= 2(k,l,km)\). This is the detailed and time consuming part.

Reviewer: H.Cohn (Bowie)

MSC:

11Y40	Algebraic number theory computations
11R29	Class numbers, class groups, discriminants
11R11	Quadratic extensions
11E16	General binary quadratic forms
11E20	General ternary and quaternary quadratic forms; forms of more than two variables

Keywords:

computation; ternary quadratic forms; 2-class group; ambiguous binary forms

Citations:

Zbl 0473.68030

Software:

Magma

References:

[1]	Bosma, W., Cannon, J.J., Playoust, C., The Magma algebra system I: the user language, J. Symbolic Comput. (to appear). · Zbl 0898.68039
[2]	Bosma, W. and Stevenhagen, P., Density computations for real quadratic units, Math. Comp.65 (1996), no. 215, 1327-1337. · Zbl 0859.11064
[3]	Cohen, H., A course in computational algebraic number theory, 138, 1993. · Zbl 0786.11071
[4]	Cohen, H., Diaz, F.Diaz, y, Olivier, M., 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. · Zbl 0822.11086
[5]	Cox, D.A., Primes of the form x2 + ny2, Wiley-Interscience, 1989. · Zbl 0701.11001
[6]	Düllmann, S., Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Dissertation, Universität des Saarlandes, Saarbrücken, 1991.
[7]	Gauss, C.F., Disquisitiones Arithmeticae, Gerhard Fleischer, Leipzig, 1801.
[8]	Hafner, J., McCurley, K., A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc.2 (1989), no. 4, 837-850. · Zbl 0702.11088
[9]	Lagarias, J.C., Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. of Algorithms1 (1980),142-186. · Zbl 0473.68030
[10]	Lagarias, J.C., 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. · Zbl 0446.10014
[11]	Shanks, D., Gauss’s ternary form reduction and the 2-Sylow subgroup, Math. Comp.25 (1971), no. 116, 837-853Erratum: Math. Comp.32 (1978), 1328-1329. · Zbl 0386.12006
[12]	Stevenhagen, P., The number of real quadratic fields having units of negative norm, Exp. Math.2 (1993), no. 2,121-136. · Zbl 0792.11041
[13]	Stevenhagen, P., A density conjecture for the negative Pell equation, ComputationalAlgebra and Number Theory, Sydney1992, Kluwer Academic Publishers, 1995, pp. 187-200. · Zbl 0838.11066