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
≈8 min read
Feeds square-root algorithms

(q−1)/2Squares mod pExactly half the non-zero residues modulo an odd prime are squares.

a^(p−1)/2Euler's criterionEquals ±1 and identifies the Legendre symbol in one modular exponentiation.

O(ℓ²)Jacobi symbolComputable in gcd time without factoring the modulus — the key algorithmic fact.

(p/q)(q/p)ReciprocityEquals (−1)^{((p−1)/2)((q−1)/2)}: two odd primes, one sign rule.

Executive summary

An element α ∈ ℤ*_n is a quadratic residue if α = β² 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.

Prime modulusLegendre (a|p)

+1 if a is a non-zero square, −1 if not, 0 if p ∣ a. Decided by one exponentiation.

Composite modulusJacobi (a|n)

Product of Legendre symbols over the prime factorization — but computable without it.

ReciprocitySign flip rule

Lets the symbol be evaluated by repeated reduction and swapping, like Euclid's algorithm.

Hard problemQuadratic residuosity

Jacobi symbol +1 does not imply square. Distinguishing the two cases modulo n = pq is believed hard.

Contents

Quadratic residues modulo a prime

Theorem T1

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.

Theorem T2

Euler's criterion

a^(p−1)/2 ≡ (a ∣ p) (mod p)for p odd and p ∤ a; the value is +1 for a quadratic residue and −1 for a non-residue

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.

The Legendre symbol
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)^(p²−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 2^r 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.

Contents

Quadratic reciprocity

Theorem T3

Law of quadratic reciprocity

(p ∣ q)(q ∣ p) = (−1)^{((p−1)/2)·((q−1)/2)}for distinct odd primes p and q

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 = 3³, so this is (3 ∣ 37)³ = (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.

Contents

The Jacobi symbol

Definition D1

Jacobi symbol

(a ∣ n) = ∏_i (a ∣ p_i)^e_i for odd n = ∏ p_i^e_iThe definition uses the factorization, but the value can be computed without it.

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.

Contents

Residuosity modulo a composite, and its cryptographic use

Structure of ℤ*n for n = pq, p and q odd primes
Subset	Size	Jacobi symbol	Actually a square?
QR_n	φ(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 QR_n 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.

Contents

Quick reference and FAQ

Symbol evaluation rules
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	2^r roots, r = number of odd prime factors	n odd

Why compute the Jacobi symbol rather than use Euler's criterion?

For a prime modulus both work, but Euler's criterion costs a modular exponentiation, O(ℓ³), while the Jacobi algorithm costs O(ℓ²) — a factor of ℓ faster. For composite moduli, exponentiation is not even a valid test, so the Jacobi algorithm is the only option.

Does a Jacobi symbol of +1 ever prove residuosity?

Only when the modulus is prime, or when the factorization is known and every Legendre symbol is checked. Treating +1 as proof of residuosity for a composite modulus is a real and exploited error.

What is the connection to primality testing?

The Solovay–Strassen test compares a^(n−1)/2 mod n with the Jacobi symbol (a ∣ n). They agree for all a exactly when n is prime, giving a probabilistic test with error at most 1/2 per round. Miller–Rabin is strictly stronger and is preferred in practice.

How do I actually extract a square root once I know one exists?

For p ≡ 3 (mod 4) the root is a^(p+1)/4. For the general case use Tonelli–Shanks, which is treated in the companion page on computing modular square roots.

Contents

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

Executive summary

Quadratic residues modulo a prime

The squares form a subgroup of index two

Euler's criterion

Quadratic reciprocity

Law of quadratic reciprocity

The Jacobi symbol

Jacobi symbol

Residuosity modulo a composite, and its cryptographic use

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning