Binary quadratic forms and class groups

A binary quadratic form f = (a, b, c) is the polynomial ax^2 + bxy + cy^2 with integer coefficients; its discriminant is D = b^2 - 4ac, which is congruent to 0 or 1 modulo 4. The group \mathrm{SL}_2(\mathbb{Z}) acts on forms by linear substitution of the variables, preserving the discriminant, and two forms in the same orbit are equivalent. Only positive definite forms (D < 0, a > 0) are supported by qfb and treated here. The standard references are [Buell1989], [Coh1996, Chapter 5] and [Cox2013].

Reduction#

The bound follows from |D| = 4ac - b^2 \ge 4a^2 - a^2 = 3a^2. The existence and uniqueness are classical [Coh1996, §5.3]. The reduction algorithm alternates two transformations:

Each exchange in step 2 decreases a, and after the first step the algorithm behaves like a Euclidean algorithm on the coefficients, with O(\log(a/\sqrt{|D|}) + 1) iterations. qfb_reduce implements it with fmpz arithmetic; the result of a composition is already nearly reduced, so in the class group computations below a reduction costs only a few steps.

Reduced forms and the class number#

The primitive forms of discriminant D (those with \gcd(a, b, c) = 1) modulo equivalence form a finite abelian group under composition, the form class group \mathrm{Cl}(D), of order the class number h(D). By Theorem 2, h(D) is the number of primitive reduced forms, and these can be listed by searching |b| \le a \le \sqrt{|D|/3} with b \equiv D \pmod 2 and a \mid (b^2 - D)/4, c = (b^2 - D)/(4a) \ge a. FLINT does this in two ways, both in O(|D|^{1/2 + o(1)}) operations:

• by b (qfb_reduced_forms): sieve the factorisations of (b^2 - D)/4 for all b at once, using the square roots of D modulo each small prime p (the b for which p divides (b^2 - D)/4 form arithmetic progressions), and read off the divisors a;
• by a (qfb_reduced_forms_large): factor 4a for all a by sieving, and for each a enumerate the square roots b of D modulo 4a with n_sqrtmodn. This needs only the primes up to |D|^{1/4} and is used for large |D|.

Asymptotically faster methods for h(D), of complexity about |D|^{1/4} (Shanks' baby-step giant-step on the analytic class number formula) or subexponential (index calculus), are not implemented.

Composition#

Gauss composition of two primitive forms f_1 = (a_1, b_1, c_1) and f_2 = (a_2, b_2, c_2) of discriminant D is as follows (Dirichlet's composition, see [Cox2013, §3]). Let g = \gcd(a_1, a_2, (b_1 + b_2)/2) and find B with

Then f_1 f_2 is the class of (a_1 a_2/g^2, B, (B^2 - D) g^2/(4 a_1 a_2)). The coefficients of this form are of the size of |D|, and a reduction brings them back to \sqrt{|D|}.

Shanks' NUCOMP [Sha1989] avoids the large intermediate form. It computes the same quantities, but stops the extended Euclidean algorithm that determines B halfway, when the remainders reach L = \lfloor |D|^{1/4} \rfloor, and assembles from the partial cofactors a form that is already nearly reduced. All intermediate numbers then have about half the size, which roughly halves the cost of a composition followed by a reduction. FLINT follows the presentation of Jacobson and van der Poorten [JvdP2002] (qfb_nucomp), with the specialisation NUDUPL for squaring (qfb_nudupl), and uses fmpz_xgcd_partial for the partial Euclidean algorithm, a variant of Lehmer's algorithm. Powers are computed by binary powering with NUDUPL, NUCOMP and a reduction after each step (qfb_pow_ui, qfb_pow).

Prime forms#

For a prime p such that D is a square modulo 4p, there is a form (p, b, c) of discriminant D with 0 \le b \le p, obtained from a square root of D modulo p (qfb_prime_form). These prime forms correspond to the prime ideals of norm p, and the prime forms with p below a bound of order \log^2 |D| generate the class group under the generalised Riemann hypothesis: Bach [Bach1990] proved that p \le 6 \log^2 |D| suffices; see also [BD1992].

Orders and the exponent#

The order of an element f of a finite group can be found by an analogue of Pollard's p - 1 method when it is smooth [Sut2007].

Stage 1. Let E = \prod_{p \le B_1} p^{\lfloor \log_p B_1 \rfloor}. If f^E = 1, then the order of f divides E, and it is found by removing the prime factors of E one at a time: for each prime p, raise f^{E/p^{k}} to successive powers of p until the identity appears. FLINT accumulates E in products of four primes, doubles the number of primes in each round, and saves intermediate powers so that the exact order can be found without starting again.

Stage 2. If f^E \ne 1, the order of h = f^E may still be a single prime q \le B_2. With m \approx \sqrt{B_2}, store the baby steps h^j for odd j < m in a hash table and compute the giant steps h^{2im}. Since the table is searched for a form or its inverse (equal a and |b|), a match h^{2im} = h^{\pm j} gives h^{2im \mp j} = 1, so the baby steps need only cover half of the residues, and odd j suffice because q is odd. The candidate 2im \mp j is accepted if it is prime.

Exponent. The exponent \lambda of \mathrm{Cl}(D) is the least common multiple of the orders of its elements, a multiple of the order of every element and a divisor of h(D). Sutherland's Algorithm 8.1 [Sut2007] computes it from random elements, here prime forms: each new form is first raised to the exponent \lambda' found so far, so that only the missing part of its order has to be found, and \lambda' \gets \lambda' \cdot \operatorname{ord}(f^{\lambda'}). With prime forms for all primes up to Bach's bound, the result is the exponent assuming GRH; with a fixed number of random primes, it is the exponent with high probability. When D is not fundamental, a prime form may be imprimitive; it is then divided by its content, which changes the discriminant to D/p^2.

Use in FLINT#