Engineering / Mathematics — Quadratic Residues
Computing Modular Square Roots: Prime Modulus
Extracting square roots modulo a prime, the easy case for p congruent to 3 mod 4, and the randomised algorithm in general.
Executive summary
For primes congruent to 3 modulo 4, a square root is a single exponentiation. For primes congruent to 1 modulo 4 the problem is genuinely harder and requires a randomised algorithm.
The general method needs a quadratic non-residue, which is found by random search since no deterministic method is known unconditionally.
Learning objectives
- Derive the direct formula for p congruent to 3 mod 4.
- State the general randomised algorithm.
- Explain why finding a non-residue requires randomness.
01The easy case
Square roots for p ≡ 3 (mod 4)
If p ≡ 3 (mod 4) and a is a quadratic residue modulo p, then
x = a^{(p+1)/4} mod p
satisfies x² ≡ a (mod p).
Verification: x² = a^{(p+1)/2} = a · a^{(p−1)/2} = a · 1 = a, using Euler's criterion in the last step. The exponent (p+1)/4 is an integer exactly because p ≡ 3 (mod 4).
p ≡ 3 (mod 4) ⇒ √a = a^{(p+1)/4} mod p02The general case
For p ≡ 1 (mod 4) no analogous closed form exists. The standard method writes p − 1 = 2^s · q with q odd and works down the powers of two, using a known non-residue to correct at each stage.
Square root modulo a prime, general case
prime p, quadratic residue ax with x² ≡ a (mod p)- Write p − 1 = 2^s · q with q odd.
- Find a quadratic non-residue z by random search.
- Set c = z^q, x = a^{(q+1)/2}, t = a^q, m = s.
- While t ≠ 1:
- Find the least i < m with t^{2^i} = 1.
- Set b = c^{2^{m−i−1}}, then x = xb, t = tb², c = b², m = i.
- Return x.
expected O(len(p)³) bit operationsThe algorithm maintains the invariant that x² = at with t of decreasing 2-power order, driving t to 1 and leaving x as the root.
03Why randomness is needed
Half of all units are non-residues, so random search finds one after two attempts on average. But producing one deterministically is open.
| Approach | Status |
|---|---|
| Random search | Expected two attempts; the practical method |
| Smallest non-residue | Under the generalised Riemann hypothesis, bounded by O((log p)²) |
| Deterministic, unconditional | No polynomial-time method known |
So square root extraction modulo a prime is in ZPP but not known to be in P — one of the cleaner examples of a problem where randomisation is not obviously removable. Choosing p ≡ 3 (mod 4) sidesteps the issue entirely, which is the practical resolution.
04Frequently asked questions
How many square roots does a residue have modulo a prime?
Exactly two, x and −x, since the polynomial X² − a has at most two roots over a field and both signs work. They are distinct because p is odd.
Which root is canonical?
There is no universal convention. For p ≡ 3 (mod 4) a natural choice is the root that is itself a quadratic residue, since exactly one of the pair is. Otherwise implementations pick the smaller representative.
Is the general algorithm related to polynomial factorisation?
Closely. Extracting a square root modulo p is factoring X² − a over the field of p elements, and the equal-degree factorisation step of Cantor–Zassenhaus uses the same random-element-and-exponentiate structure.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 292-295.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.