Quadratic Fields
Composition of Binary Quadratic Forms
Gauss composition as the group law on form classes, its practical computation, and reduction between compositions.
Engineering / MathematicsQuadratic Fields2 min readKV-MATH-0603
Composition is the group law on form classes, corresponding to ideal multiplication. Gauss's original formulation is intricate; the modern treatment is a short computation with the extended Euclidean algorithm.
What it computes
The computation
Composition of two forms
- Compute a GCDOf the two first coefficients and the average of the middle ones, with Bezout coefficients.
- Solve congruencesDetermine the middle coefficient of the composite from congruence conditions.
- Form the productThe first coefficient is the product of the originals divided by the square of the GCD.
- ReduceApply reduction immediately.
Squaring
Composing a form with itself admits a simplified formula, worth implementing separately because exponentiation by repeated squaring is dominated by squarings.
NUCOMP
Shanks's NUCOMP algorithm interleaves reduction with composition, keeping intermediate values small throughout rather than reducing afterwards. It is substantially faster for large discriminants and is the standard method in serious implementations.
| Method | Intermediate size | Speed |
|---|---|---|
| Compose then reduce | Grows to the product of the coefficients | Adequate for small discriminants |
| NUCOMP | Bounded near the square root of the discriminant | Substantially faster for large discriminants |
Uses
Composition is the group operation underlying class group structure computation, element orders in the class group, and Shanks's class group factoring method, where an ambiguous form reveals a factorisation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 5.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.