Euclidean Algorithms and Congruences
Solving Quadratic Congruences
Reducing a general quadratic congruence to a square root extraction, and handling the degenerate cases the reduction assumes away.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0521
A general quadratic congruence reduces to extracting a square root, by exactly the completion of the square used over the reals. The interest lies entirely in the cases where the reduction breaks down.
The reduction
Solving a quadratic congruence modulo an odd prime
- NormaliseMultiply through by the inverse of a, obtaining a monic congruence.
- Complete the squareSubstitute to remove the linear term; the constant becomes the discriminant divided by four.
- Test solvabilityEvaluate the Legendre symbol of the discriminant. If -1, there is no solution.
- Extract the rootApply Shanks-Tonelli.
- Back-substituteRecover the two solutions.
Degenerate cases
| Condition | Behaviour |
|---|---|
| p divides a | Congruence is linear, not quadratic; solve directly |
| p = 2 | Completion of the square fails; enumerate the two residues |
| Discriminant zero mod p | A single repeated root |
| Legendre symbol -1 | No solution |
Prime powers
Modulo a prime power, solve first modulo the prime, then lift. The lifting is straightforward when the derivative of the polynomial at the root is invertible — the non-degenerate case. When it is not, several roots may lift to each root or none may, and the case analysis must be done explicitly.
Where this appears
Quadratic congruences arise in quadratic sieve initialisation, where the sieve positions are the roots of a quadratic modulo each factor base prime, and in form reduction when representing an ideal by a binary quadratic form.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.4.4. 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.