Engineering/Mathematics/Number theory
Quadratic Residues and Quadratic Reciprocity
Deciding whether a number is a square modulo a prime takes one exponentiation; modulo a composite of unknown factorization it is believed to be intractable. That gap is a cryptographic primitive in its own right, and reciprocity is what makes the easy side fast.
- Core theory
- Number theory
- Cryptographic primitive
- ≈15 min read
- Feeds square-root algorithms
01
Executive summary
An element α ∈ ℤ*n is a quadratic residue if α = β2 for some β. Modulo an odd prime the squares form a subgroup of index 2, detected in polynomial time by Euler's criterion. Modulo a composite, the picture splits along the prime factorization, and the detection problem becomes hard without it.
The Legendre symbol records residuosity modulo a prime; the Jacobi symbol extends it multiplicatively to odd composite moduli. Crucially, the Jacobi symbol can be computed by a Euclid-like algorithm that never factors the modulus — but it is then no longer a reliable indicator of residuosity, and that discrepancy is exactly what the quadratic residuosity assumption exploits.
+1 if a is a non-zero square, −1 if not, 0 if p ∣ a. Decided by one exponentiation.
Product of Legendre symbols over the prime factorization — but computable without it.
Lets the symbol be evaluated by repeated reduction and swapping, like Euclid's algorithm.
Jacobi symbol +1 does not imply square. Distinguishing the two cases modulo n = pq is believed hard.
02
Quadratic residues modulo a prime
The squares form a subgroup of index two
For an odd prime p, the squaring map on ℤ*p is two-to-one, since β and −β have the same square and these are distinct. Its image, the set of quadratic residues, therefore has (p−1)/2 elements. In terms of a generator g, the residues are exactly the even powers of g.
Euler's criterion
Proof: the left side squares to 1, so it is ±1. It equals 1 exactly when the order of a divides (p−1)/2, which happens exactly for the even powers of a generator.
| Property | Statement | Reading |
|---|---|---|
| Definition | (a ∣ p) ∈ {0, ±1} | 0 when p ∣ a, otherwise ±1 by residuosity |
| Multiplicativity | (ab ∣ p) = (a ∣ p)(b ∣ p) | Non-residue × non-residue = residue |
| Periodicity | (a ∣ p) depends only on a mod p | Reduce before evaluating |
| First supplement | (−1 ∣ p) = (−1)(p−1)/2 | −1 is a square exactly when p ≡ 1 (mod 4) |
| Second supplement | (2 ∣ p) = (−1)(p2−1)/8 | 2 is a square exactly when p ≡ ±1 (mod 8) |
Counting square roots
A quadratic residue modulo an odd prime has exactly two square roots, ±β. Modulo n with r distinct odd prime factors, CRT multiplies the choices: a residue has 2r square roots. For n = pq that is four, and finding two roots whose difference is not ± the other yields a factorization by a gcd — the core of the Rabin cryptosystem's security reduction.
03
Quadratic reciprocity
Law of quadratic reciprocity
Equivalently: (p ∣ q) = (q ∣ p) unless both p and q are congruent to 3 (mod 4), in which case the two symbols differ in sign. Gauss called it the theorema aureum and published six proofs; more than two hundred are now known.
The result is remarkable in that it relates two questions with no obvious connection — whether p is a square modulo q, and whether q is a square modulo p. Its practical value is entirely algorithmic: combined with multiplicativity and the two supplements, it lets a symbol be evaluated by alternately reducing and swapping arguments, exactly like the Euclidean algorithm.
Worked evaluation of (37 ∣ 101)
Both are prime and 101 ≡ 1 (mod 4), so reciprocity gives (37 ∣ 101) = (101 ∣ 37) = (27 ∣ 37). Now 27 = 33, so this is (3 ∣ 37)3 = (3 ∣ 37). Since 37 ≡ 1 (mod 4), reciprocity again gives (3 ∣ 37) = (37 ∣ 3) = (1 ∣ 3) = 1. So 37 is a quadratic residue modulo 101 — established without computing any square root or exponentiation.
04
The Jacobi symbol
Jacobi symbol
The Jacobi symbol inherits multiplicativity in both arguments, the two supplements, and the reciprocity rule with p, q replaced by any odd coprime m, n. Those properties are enough to drive a gcd-style algorithm.
Jacobi symbol (a ∣ n), n odd positive
- a ← a mod n; t ← 1
- while a ≠ 0:
- while a even: a ← a/2; if n ≡ 3,5 (mod 8): t ← −t // second supplement
- swap(a, n); if a ≡ n ≡ 3 (mod 4): t ← −t // reciprocity
- a ← a mod n
- return t if n = 1 else 0
O(ℓ²) bit operations for ℓ-bit inputs — the same order as the Euclidean algorithm, and with no factoring of n at any point.
The symbol is not a residuosity test for composite moduli
If (a ∣ n) = −1 then a is definitely a non-residue. But (a ∣ n) = +1 only says an even number of the Legendre symbols were −1. For n = pq, the elements with Jacobi symbol +1 split evenly into true squares and products of two non-residues, and no efficient way to tell them apart without the factorization is known.
05
Residuosity modulo a composite, and its cryptographic use
| Subset | Size | Jacobi symbol | Actually a square? |
|---|---|---|---|
| QRn | φ(n)/4 | +1 | Yes — four square roots each |
| Pseudo-squares | φ(n)/4 | +1 | No — non-residue mod both p and q |
| Mixed type A | φ(n)/4 | −1 | No — residue mod p only |
| Mixed type B | φ(n)/4 | −1 | No — residue mod q only |
The Jacobi symbol separates the bottom two rows from the top two in polynomial time; separating the first row from the second is the quadratic residuosity problem.
- Quadratic residuosity assumption. Given n = pq and a with (a ∣ n) = +1, deciding whether a is a square is intractable without the factorization. Goldwasser–Micali encryption is built directly on this and was the first semantically secure public-key scheme.
- Blum integers. When p ≡ q ≡ 3 (mod 4), squaring is a permutation of QRn and −1 has Jacobi symbol +1 while being a non-residue. This gives clean square-root extraction with the factorization, and underpins the Blum–Blum–Shub generator and Rabin signatures.
- Square roots reveal factors. Any algorithm producing a square root of a random square modulo n can be turned into a factoring algorithm with probability 1/2 per query — extracting square roots modulo a composite is computationally equivalent to factoring.
06
Quick reference and FAQ
| Rule | Statement | Condition |
|---|---|---|
| Euler | (a ∣ p) ≡ a(p−1)/2 (mod p) | p odd prime |
| Multiplicative | (ab ∣ n) = (a ∣ n)(b ∣ n) | n odd |
| −1 | (−1 ∣ n) = 1 ⟺ n ≡ 1 (mod 4) | n odd |
| 2 | (2 ∣ n) = 1 ⟺ n ≡ ±1 (mod 8) | n odd |
| Reciprocity | (m ∣ n)(n ∣ m) = (−1)((m−1)/2)((n−1)/2) | m,n odd, coprime |
| Root count mod p | 2 roots for each residue | p odd prime |
| Root count mod n | 2r roots, r = number of odd prime factors | n odd |
Why compute the Jacobi symbol rather than use Euler's criterion?
Does a Jacobi symbol of +1 ever prove residuosity?
What is the connection to primality testing?
How do I actually extract a square root once I know one exists?
08
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapters 12 and 13.
- K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990 — Chapter 5 for reciprocity proofs.
- S. Goldwasser and S. Micali, 'Probabilistic encryption', J. Comput. Syst. Sci. 28 (1984) 270–299.
- A. J. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996 — §2.4.5 and §3.4.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: quadratic-residues-and-reciprocityReview cycle: annual