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

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)


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


Zbl 0473.68030


Full Text: DOI Numdam Numdam EuDML EMIS


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.