Euclidean Algorithms and Congruences
Legendre, Jacobi and Kronecker Symbol Computation
The three quadratic symbols, their differing meanings, and the reciprocity-based algorithm that computes them without factoring.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0519
The quadratic symbols answer whether an element is a square. The critical computational fact is that the Jacobi symbol can be evaluated in Euclidean time without factoring either argument — which is what makes it usable inside sieving methods.
Three symbols, three meanings
- Legendre symbol
- Defined for an odd prime modulus. Value 1 if the argument is a non-zero square modulo p, -1 if not, 0 if p divides it. This one genuinely decides squareness.
- Jacobi symbol
- Extends to odd composite moduli as the product of Legendre symbols over the prime factorisation. Value 1 does NOT imply squareness.
- Kronecker symbol
- Extends further to all integers including even and negative moduli. Used for field discriminants.
The algorithm
Quadratic reciprocity gives a Euclidean-style algorithm. Each step removes factors of two, applies the reciprocity flip, and reduces — exactly parallel to the GCD.
Jacobi symbol by reciprocity
- ReduceReduce the numerator modulo the denominator.
- Extract twosRemove factors of two, adjusting the sign using the supplementary law based on the denominator modulo eight.
- FlipSwap the arguments, adjusting the sign by the reciprocity law when both are congruent to three modulo four.
- RepeatUntil the numerator is zero or one.
Applications
| Application | Role of the symbol |
|---|---|
| Factor base selection | Keep only primes for which the target is a residue |
| Prime decomposition in quadratic fields | The Kronecker symbol of the discriminant decides split, inert or ramified — see decomposition |
| Solovay-Strassen compositeness | Compare the Jacobi symbol against an Euler pseudoprime test |
| Square root extraction | Confirm a square root exists before running Shanks-Tonelli |
Edge cases
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.4.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.