Square Roots Modulo a Prime

Q: What happens if I run Tonelli-Shanks on a composite modulus?

It fails silently or loops, because the algorithm assumes the group structure of a field. Square roots modulo a composite are computed instead by finding roots modulo each prime power and combining by CRT — which requires the factorisation, and is why square roots modulo a composite are computationally equivalent to factoring.

Q: Is Cipolla's algorithm better than Tonelli-Shanks?

Cipolla works in a quadratic extension and costs O(log p) extension-field multiplications regardless of the 2-part of p−1. It wins when p−1 is divisible by a very large power of 2; Tonelli–Shanks wins in the common case where that power is small.

Q: How do I get the other square root?

The two roots are x and p−x, and there are exactly two for a non-zero residue modulo an odd prime. Implementations usually return the smaller, but this is convention, not mathematics — check the documentation before relying on it.

Executive summary

Extracting a square root when the modulus is prime

When p ≡ 3 (mod 4) a square root is a single modular exponentiation. The general case is harder because the 2-part of the group (ℤ/pℤ)* is non-trivial; Tonelli–Shanks resolves it by walking down that 2-part one level at a time, using a known non-residue as a lever. Cornacchia's algorithm then converts a modular square root of −d into an integer representation x² + dy² = p.

Learning objectives

Apply the congruence shortcuts where they exist.
Explain the 2-adic structure that Tonelli–Shanks exploits.
Analyse the algorithm's cost in terms of the 2-part of p−1.
Use Cornacchia's algorithm to represent a prime by a quadratic form.

Section 01Shortcuts by congruence class

Write p − 1 = 2^eq with q odd. The difficulty is governed entirely by e.

Square-root strategies by the 2-part of p−1
Case	e	Method	Cost
p ≡ 3 (mod 4)	1	x = a^(p+1)/4 mod p	One exponentiation
p ≡ 5 (mod 8)	2	One exponentiation plus a correction by a power of 2	One exponentiation
p ≡ 1 (mod 8)	≥ 3	Tonelli–Shanks or Cipolla	O(e²) extra multiplications

Why 3 mod 4 works

If a is a residue then a^(p−1)/2 = 1, so (a^(p+1)/4)² = a^(p+1)/2 = a · a^(p−1)/2 = a. The exponent (p+1)/4 is an integer precisely because p ≡ 3 (mod 4).

Section 02The Tonelli–Shanks algorithm

AlgorithmTonelli–Shanksin: prime p, residue a → out: x with x² ≡ a (mod p)

Verify (a/p) = 1; otherwise no square root exists.
Write p − 1 = 2^eq with q odd.
Find a quadratic non-residue n by random search; set z ← n^q mod p. z generates the 2-Sylow subgroup.
Set y ← z, r ← e, x ← a^(q−1)/2, b ← a x², x ← a x.
While b ≠ 1: find the least m with b^{2^m} = 1. m measures the remaining 2-power obstruction.
Set t ← y^{2^(r−m−1)}, y ← t², r ← m.
Set x ← x t and b ← b y.
Return x, with x² ≡ a (mod p).

Finding the non-residue

No deterministic method for finding a non-residue is known that is unconditionally fast, so random search is used: half of all residues qualify, so the expected number of trials is 2. This randomisation is the only non-deterministic element of the algorithm, and it does not affect correctness — only running time.

Section 03Cornacchia's algorithm

Given a prime p and d > 0 with −d a residue modulo p, Cornacchia's algorithm decides whether x² + dy² = p is solvable and produces the solution. It is a partial Euclidean algorithm with an early stop.

AlgorithmCornacchia's algorithmin: prime p, d > 0 → out: (x, y) with x² + dy² = p, or none

Compute a square root x₀ of −d modulo p with p/2 < x₀ < p.
Run the Euclidean algorithm on (p, x₀), stopping at the first remainder a < √p. The early stop is the essential step.
Set t ← p − a². If d does not divide t, report no solution.
If t/d is not a perfect square, report no solution.
Return (x, y) = (a, √(t/d)).

Where this is needed

Cornacchia's algorithm supplies the representations used to construct elliptic curves with prescribed complex multiplication — the foundation of the CM method for curve generation and of Atkin's primality test.

ReferenceFrequently asked questions

What happens if I run Tonelli-Shanks on a composite modulus?

It fails silently or loops, because the algorithm assumes the group structure of a field. Square roots modulo a composite are computed instead by finding roots modulo each prime power and combining by CRT — which requires the factorisation, and is why square roots modulo a composite are computationally equivalent to factoring.

Is Cipolla's algorithm better than Tonelli-Shanks?

Cipolla works in a quadratic extension and costs O(log p) extension-field multiplications regardless of the 2-part of p−1. It wins when p−1 is divisible by a very large power of 2; Tonelli–Shanks wins in the common case where that power is small.

How do I get the other square root?

The two roots are x and p−x, and there are exactly two for a non-zero residue modulo an odd prime. Implementations usually return the smaller, but this is convention, not mathematics — check the documentation before relying on it.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.