← Wiki Index / Computation & Algorithms / Tonelli–Shanks Algorithm
💻 Computation & Algorithms

Tonelli–Shanks Algorithm

The Tonelli–Shanks algorithm is a randomized polynomial-time number-theoretic algorithm for computing modular square roots modulo an odd prime p.

The Tonelli–Shanks algorithm (independently discovered by Italian mathematician Alberto Tonelli in 1891 and modernized by Daniel Shanks in 1973) is a fundamental modular arithmetic algorithm that solves the quadratic congruence x2 ≡ n (mod p) for an odd prime p, given an integer n that is a quadratic residue modulo p. While special prime congruences such as p ≡ 3 (mod 4) admit a direct single-exponentiation formula x ≡ n(p+1)/4 (mod p), arbitrary odd primes—especially those with high 2-adic valuation p - 1 = Q × 2S—require iterative group-order reduction provided by Tonelli–Shanks.

In modern computational number theory, cryptography, and integer factorization, Tonelli–Shanks is widely used for point decompression on elliptic curves over prime fields, Quadratic Sieve and Number Field Sieve factor-base sieving, and zero-knowledge proof arithmetic.

Group-Theoretic Mechanism and Step-by-Step Procedure

First, Euler's criterion verifies that n is a quadratic residue modulo p by checking n(p-1)/2 ≡ 1 (mod p). Next, factor p - 1 = Q × 2S with Q odd, and find any quadratic non-residue z (satisfying z(p-1)/2 ≡ -1 (mod p); picking z at random succeeds with probability 1/2 per trial).

The algorithm maintains loop invariants inside the cyclic 2-Sylow subgroup of order 2S:

  1. Initialize c ≡ zQ (mod p) (a primitive 2S-th root of unity), R ≡ n(Q+1)/2 (mod p), t ≡ nQ (mod p), and M = S.
  2. Notice the invariant R2 ≡ n × t (mod p) holds initially because R2 = nQ+1 = n × t, and t has multiplicative order dividing 2M-1.
  3. While t ≠ 1 (mod p), find the smallest positive integer i (1 <= i < M) such that t2i ≡ 1 (mod p).
  4. Set b ≡ c2M - i - 1 (mod p), then update M ← i, c ← b2 (mod p), t ← t × c (mod p), and R ← R × b (mod p).
  5. Because t and c have matching 2-adic order 2i, multiplying them halves (or directly reduces) the 2-adic order of t in every iteration until t ≡ 1 (mod p), leaving R2 ≡ n (mod p)!

Computational Complexity and Cipolla's Alternative

Finding a quadratic non-residue z takes O(1) expected trials (each checked in O(log p) multiplications), and the main loop executes at most S = v2(p - 1) iterations, performing O(S2) modular multiplications in the worst case. Total expected running time is O(log2 p + S2 log p) modular operations—practically instantaneous for 256-bit cryptographic primes when S is small, though Cipolla's algorithm (working in quadratic extension field GF(p2)) can outperform Tonelli–Shanks when S is very large (such as Proth or NTT-friendly primes).

Relationship to Pocklington's Method and Deterministic Variants

When the prime modulus satisfies p ≡ 5 (mod 8), Atkin's or Legendre's refinement computes modular square roots in a single exponentiation without searching for a non-residue, while for general p ≡ 1 (mod 8) with moderate 2-adic exponent S, Tonelli–Shanks remains the standard general-purpose routine in libraries such as OpenSSL, FLINT, and Python's sympy. Note that Tonelli–Shanks solves x2 ≡ n (mod p) for prime moduli; when computing modular square roots modulo a composite modulus N = p × q (as in Rabin cryptosystems or Blum–Blum–Shub generators), one computes square roots modulo p and q separately via Tonelli–Shanks and combines them using the Chinese Remainder Theorem.

Frequently Asked Questions

When is a simpler formula available instead of Tonelli–Shanks?

Whenever p ≡ 3 (mod 4) (so S = 1), one modular exponentiation R ≡ n(p+1)/4 (mod p) solves x2 ≡ n (mod p) directly without any loop or non-residue search.

Why is Tonelli–Shanks considered a probabilistic (Las Vegas) algorithm?

Searching for a quadratic non-residue z by random sampling takes O(1) expected steps; under the Generalized Riemann Hypothesis (GRH), testing small primes up to 2 ln2 p makes the algorithm completely deterministic in polynomial time.

How is Tonelli–Shanks used in elliptic-curve cryptography?

Elliptic-curve public keys are often transmitted in compressed form (storing only the x-coordinate and one parity bit for y); the receiver evaluates x3 + ax + b (mod p) and runs Tonelli–Shanks to recover the y-coordinate.

How many solutions does x2 ≡ n (mod p) have when n is a non-zero quadratic residue?

For any odd prime p and non-zero quadratic residue n, there are two distinct solutions modulo p: R and p - R (which correspond to +R and -R mod p).

References

  1. (2015). Square Root Error and Random Walks. Prime Numbers and the Riemann Hypothesis. https://doi.org/10.1017/cbo9781316182277.013
  2. Sarkar, P., & Applied Statistics Unit, Indian Statistical Institute (2024). Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm. Advances in Mathematics of Communications. https://doi.org/10.3934/amc.2022007
  3. Paltoo, N. S. (2026). Prime-Generated Logarithmic Lamination and key-Line Rigidity Identity, Square-Root Normalization, Relative Angular Closure, and Mellin Monodromy. https://doi.org/10.2139/ssrn.7521858
🧬 Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
💡 Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision