Engineering/Mathematics/Algorithm engineering
Computing Modular Square Roots
Extracting a square root modulo a prime is a polynomial-time computation with a pleasant structure; extracting one modulo a composite is equivalent to factoring it. The same operation is easy or intractable depending only on what you know about the modulus.
- Core algorithm
- Computing
- Cryptographic primitive
- ≈15 min read
- Used in point decompression
01
Executive summary
Three related problems appear together. Computing the Jacobi symbol is cheap and never requires a factorization. Deciding residuosity is cheap modulo a prime and believed hard modulo a composite of unknown factorization. Extracting a root is polynomial time modulo a prime, and equivalent to factoring modulo a composite.
The practical picture is dominated by the shape of p−1. If p ≡ 3 (mod 4) a single exponentiation suffices, which is why elliptic-curve standards prefer such primes: point decompression from an x-coordinate is exactly a square root extraction and happens on every key exchange. For a general prime, Tonelli–Shanks walks down the 2-part of the group.
| Problem | Modulus prime | Modulus composite, factorization known | Modulus composite, factorization unknown |
|---|---|---|---|
| Jacobi symbol | O(ℓ2) | O(ℓ2) | O(ℓ2) |
| Decide residuosity | O(ℓ2) via Jacobi | polynomial | believed intractable |
| Extract a root | O(ℓ3) | polynomial via CRT | equivalent to factoring |
| Count the roots | 2 | 2r for r odd prime factors | unknown without the factorization |
02
Computing the Jacobi symbol
The Jacobi symbol is evaluated by alternately removing factors of two and applying reciprocity to swap the arguments — structurally identical to the Euclidean algorithm, and with the same cost.
Jacobi symbol (a ∣ n), n odd and positive
- t ← 1; a ← a mod n
- while a ≠ 0:
- while a is even:
- a ← a/2
- if n mod 8 ∈ {3,5}: t ← −t // second supplement
- swap(a, n)
- if a ≡ 3 (mod 4) and n ≡ 3 (mod 4): t ← −t // reciprocity
- a ← a mod n
- return t if n = 1 else 0 // 0 signals gcd(a,n) > 1
O(ℓ²) bit operations. Compare Euler's criterion, which needs a modular exponentiation at O(ℓ³) and works only for a prime modulus.
Screening before extraction
Always compute the Jacobi symbol before attempting a root extraction. A value of −1 proves no root exists and costs a factor of ℓ less than discovering the same thing by a failed exponentiation. A value of 0 means the argument shares a factor with the modulus — for a supposed prime modulus, that is itself a compositeness proof.
03
Square roots modulo a prime
The easy congruence classes
| Condition on p | Root of a quadratic residue a | Cost |
|---|---|---|
| p ≡ 3 (mod 4) | a(p+1)/4 | One exponentiation |
| p ≡ 5 (mod 8) | a(p+3)/8, corrected by a factor 2(p−1)/4 when needed | One exponentiation plus a test |
| p ≡ 1 (mod 8) | No closed form known | Tonelli–Shanks or Cipolla |
Curve and protocol standards frequently specify p ≡ 3 (mod 4) precisely so that the first row applies — for example the primes underlying several widely deployed elliptic curves.
Tonelli–Shanks for a general odd prime
- write p − 1 = 2^e·m with m odd
- find a quadratic non-residue z (random trial; expected 2 attempts)
- c ← z^m; t ← a^m; r ← a^{(m+1)/2}; k ← e
- while t ≠ 1:
- find the least i with t^{2^i} = 1
- b ← c^{2^{k−i−1}}
- r ← r·b; t ← t·b²; c ← b²; k ← i
- return r // r² = a
One exponentiation, O(ℓ³) bit operations, plus O(e²) modular multiplications in the loop. For random primes e is small, so the exponentiation dominates; for primes with a large power of two dividing p−1 the loop can matter.
- Why a non-residue is needed. The algorithm walks down the cyclic 2-Sylow subgroup of ℤ*p, and a non-residue provides a generator of that subgroup. Finding one is easy by random trial — half of all elements qualify — but no deterministic method is known without assuming the extended Riemann hypothesis.
- Cipolla's algorithm is an alternative that works in the quadratic extension Fp2, computing (x + √(x2−a))(p+1)/2. Its cost does not depend on e, making it preferable when p−1 is divisible by a large power of two.
- Both roots. Every extraction gives r and −r; protocols that need a canonical choice pick the one with even least significant bit or the smaller representative, and must specify which.
04
Prime powers and composites
Hensel lifting
If r2 ≡ a (mod pk) and p is odd with p ∤ a, then the root lifts uniquely to pk+1 via r′ = r − (r2−a)·(2r)−1 mod pk+1. Iterating doubles the precision each step, so a root modulo pk costs about the same as a root modulo p plus a few Newton steps. The prime 2 is exceptional and requires separate treatment.
For a composite modulus with known factorization, extract a root modulo each prime power and combine by the Chinese remainder theorem. Each odd prime factor contributes an independent sign, giving 2r roots for r distinct odd prime factors.
Root extraction is equivalent to factoring
Suppose an algorithm returns some square root of any given quadratic residue modulo n = pq. Choose random x, submit x2 mod n, and receive a root y. With probability 1/2, y ≢ ±x, and then gcd(x−y, n) is a proper factor. Repeating gives the factorization in expected two queries.
Design consequence
Any protocol that answers square-root queries modulo a composite is handing out a factoring oracle. The Rabin cryptosystem turns this into a feature — its security reduction to factoring is tight — but it also means Rabin decryption is completely broken by a chosen-ciphertext attack unless redundancy is added to the plaintext.
05
Where square roots are actually computed
Elliptic curve point decompression
A compressed point stores x and one bit; recovering y requires a square root of x3+ax+b modulo p. Performed on every key exchange, so its cost is a real parameter in curve selection.
Rabin cryptosystem and signatures
Encryption is squaring; decryption is root extraction using the factorization. Security is provably equivalent to factoring.
Quadratic sieve
The sieving step solves x2 ≡ n (mod p) for each factor-base prime to locate the positions where p divides the sieve polynomial.
Cornacchia's algorithm
Representing a prime as x2+dy2 starts from a square root of −d modulo p; used in complex multiplication methods for curve construction and in ECPP.
Blum–Blum–Shub generator
Iterated squaring modulo a Blum integer, with security resting on quadratic residuosity.
Goldwasser–Micali encryption
Encrypts one bit as a residue or a pseudo-square; decryption is a residuosity decision using the factorization.
Choosing primes to make this cheap
Where square roots are on a hot path, choose p ≡ 3 (mod 4). The extraction becomes a single exponentiation with a fixed exponent, which is also straightforward to implement in constant time — a requirement when the value being rooted derives from secret data.
06
Quick reference and FAQ
| Fact | Statement |
|---|---|
| Existence test | (a ∣ p) = 1 for an odd prime p |
| Root count mod p | 2, namely ±r |
| p ≡ 3 (mod 4) | r = a(p+1)/4 |
| General odd prime | Tonelli–Shanks or Cipolla |
| Prime power | Hensel lift from the prime case (odd p) |
| Composite, known factorization | CRT combine; 2r roots |
| Composite, unknown factorization | Equivalent to factoring |
| Jacobi symbol cost | O(ℓ2), no factoring |
Why does Tonelli–Shanks need a quadratic non-residue?
Is the algorithm constant time?
What happens at the prime 2?
Can I test residuosity modulo n = pq without the factorization?
08
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 13.
- A. Tonelli (1891) and D. Shanks, 'Five number-theoretic algorithms', Proc. 2nd Manitoba Conf. on Numerical Mathematics, 1972, 51–70.
- H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993 — §1.5.
- M. O. Rabin, 'Digitalized signatures and public-key functions as intractable as factorization', MIT/LCS/TR-212, 1979.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: computing-modular-square-rootsReview cycle: annual