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
≈8 min read
Used in point decompression

O(ℓ²)Jacobi symbolA Euclid-style algorithm with no factoring — the cheapest residuosity screen available.

a^(p+1)/4Easy caseWhen p ≡ 3 (mod 4), one exponentiation gives the root. This is why such primes are specified in curve standards.

O(ℓ³ + e²)Tonelli–ShanksGeneral odd prime, where 2^e ∥ p−1. Expected cost is dominated by one exponentiation.

= factoringComposite modulusProducing square roots modulo n yields the factorization of n with probability 1/2 per attempt.

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 difficulty summary
Problem	Modulus prime	Modulus composite, factorization known	Modulus composite, factorization unknown
Jacobi symbol	O(ℓ²)	O(ℓ²)	O(ℓ²)
Decide residuosity	O(ℓ²) via Jacobi	polynomial	believed intractable
Extract a root	O(ℓ³)	polynomial via CRT	equivalent to factoring
Count the roots	2	2^r for r odd prime factors	unknown without the factorization

Contents

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.

Contents

Square roots modulo a prime

The easy congruence classes

Closed-form root extraction
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 F_p², computing (x + √(x²−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.

Contents

Prime powers and composites

Theorem T1

Hensel lifting

If r² ≡ a (mod p^k) and p is odd with p ∤ a, then the root lifts uniquely to p^k+1 via r′ = r − (r²−a)·(2r)⁻¹ mod p^k+1. Iterating doubles the precision each step, so a root modulo p^k 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 2^r roots for r distinct odd prime factors.

Theorem T2

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 x² 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.

Contents

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 x³+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 x² ≡ 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 x²+dy² 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.

Contents

Quick reference and FAQ

Facts
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; 2^r roots
Composite, unknown factorization	Equivalent to factoring
Jacobi symbol cost	O(ℓ²), no factoring

Why does Tonelli–Shanks need a quadratic non-residue?

It needs a generator of the 2-Sylow subgroup of ℤ*_p, and z^m for a non-residue z supplies one. Any non-residue works, and half of all elements are non-residues, so random search finds one in two attempts on average.

Is the algorithm constant time?

Not as written — the loop count depends on the input. For secret data use the closed-form exponentiation when p ≡ 3 (mod 4), or a constant-time variant with a fixed iteration count and masked selection.

What happens at the prime 2?

Squaring modulo 2^k is four-to-one for k ≥ 3 rather than two-to-one, so the root count and the lifting rule differ. Odd residues modulo 2^k are squares exactly when they are congruent to 1 (mod 8).

Can I test residuosity modulo n = pq without the factorization?

You can compute the Jacobi symbol, which rules out residuosity when it is −1. When it is +1 no efficient decision procedure is known, and the presumed hardness of that decision is a standard cryptographic assumption.

Contents

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

Executive summary

Computing the Jacobi symbol

Square roots modulo a prime

The easy congruence classes

Prime powers and composites

Hensel lifting

Root extraction is equivalent to factoring

Where square roots are actually computed

Elliptic curve point decompression

Rabin cryptosystem and signatures

Quadratic sieve

Cornacchia's algorithm

Blum–Blum–Shub generator

Goldwasser–Micali encryption

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning