Tonelli-Shanks — computing an actual modular square root, not just whether one exists

Tonelli-Shanks computes an actual modular square root: given an odd prime p and a quadratic residue a, it returns x with x² ≡ a (mod p), including the general p ≡ 1 (mod 4) case where the simple exponentiation shortcut fails. Its cost isn't a clean O(log²p) bound: writing p - 1 = q·2^s, the number of modular multiplications is 2m + 2k + s(s-1)/4 + 1/2^(s-1) - 9 (m = bit-length of p, k = number of 1-bits in p, s = the power of 2 dividing p - 1) — dominated by s² when s is large, and close to O(log p) when s is small, which is the common case for primes you'll meet in practice.

The signal that gives it away

- You need the value of a square root mod a prime, not just a yes/no on whether one exists — that's Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks's job, not this one. Tonelli-Shanks is the step you reach for *after* Legendre already said (a/p) = +1. - The modulus p satisfies p ≡ 1 (mod 4). If instead p ≡ 3 (mod 4), you don't need this algorithm at all: the direct exponentiation shortcut works and is cheaper. Checking p % 4 first is the single most decision-relevant move — it tells you whether you can skip the whole machinery below. - Rabin decryption: recovering the plaintext requires all four square roots of the ciphertext mod n = p·q, and disambiguating which one is the real message. - Recovering an elliptic-curve point's y from a known x: given y² = x³ + a·x + b (mod p), the right-hand side is the a you feed into Tonelli-Shanks (see Elliptic Curve Fundamentals — the audit that routes to the right ECC attack). - Expressing a prime p ≡ 1 (mod 4) as a sum of two squares a² + b²: the first step is finding a square root of -1 mod p, which is exactly a Tonelli-Shanks call with a = p - 1 (see Gaussian Integers — factoring sums of two squares in Z[i]). - The modulus is composite, not prime — that's a signal to factor first and route through Chinese Remainder Theorem — recombining residues across coprime moduli, not a signal to run Tonelli-Shanks directly (see "What does NOT work" below).

How to exploit it

1. Gate it with Legendre first. Confirm (a/p) = 1 via Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks (pow(a, (p-1)//2, p) == 1) before doing anything else. This isn't optional bookkeeping — the algorithm's internal logic assumes a root exists, and running it on a non-residue produces either an outright error or, in weaker implementations, a silently wrong answer. A correct implementation checks this and raises rather than continuing. 2. Take the shortcut when you can. If p % 4 == 3, the root is just pow(a, (p+1)//4, p) — one modular exponentiation, O(log p), no need for the full algorithm below. This covers a large share of primes you'll meet in practice and is worth checking before reaching for anything heavier. 3. Otherwise, run the general algorithm for the p ≡ 1 (mod 4) case: - Write p - 1 = q·2^s with q odd (factor out all powers of 2). - Find any quadratic non-residue z mod p (just scan z = 2, 3, 4, ... checking pow(z, (p-1)//2, p) == p-1; finding one typically takes only a couple of Legendre-symbol checks on average — non-residues are common, not rare). - Iterate the standard reduction loop that repeatedly halves the order of t until it collapses to 1, updating (m, c, t, r) each round; r converges to a root of a. ``python def tonelli(a, p): a %= p if pow(a, (p - 1) // 2, p) != 1: raise ValueError("no root") # Legendre check baked in — fail loud, not silent if p % 4 == 3: return pow(a, (p + 1) // 4, p) # shortcut, skip the rest entirely q, s = p - 1, 0 while q % 2 == 0: q //= 2 s += 1 z = 2 while pow(z, (p - 1) // 2, p) != p - 1: # find a non-residue z += 1 m, c, t, r = s, pow(z, q, p), pow(a, q, p), pow(a, (q + 1) // 2, p) while t != 1: i, t2 = 0, t while t2 != 1: t2 = t2 * t2 % p i += 1 b = pow(c, 1 << (m - i - 1), p) m, c, t, r = i, b * b % p, t * b * b % p, r * b % p return r ` In SageMath, skip the reimplementation entirely and call Mod(a, p).sqrt() — it dispatches to the fast path automatically and is what you want under CTF time pressure unless the challenge specifically requires a from-scratch implementation. 4. **Remember there are always two roots**, x and p - x (i.e. ±x). The algorithm returns one of them arbitrarily; if the target context has a way to distinguish the "right" one — a parity bit encoded elsewhere, a range constraint, a checksum — you must test both against that constraint. Don't assume the returned root is automatically the semantically correct one. 5. **For a composite modulus**, do not hand n to Tonelli-Shanks directly. Factor n into its prime components, run Tonelli-Shanks on a mod p_i for each prime factor p_i` separately, then recombine the per-prime roots via Chinese Remainder Theorem — recombining residues across coprime moduli. This is also how Rabin decryption's four candidate roots arise: two choices of sign for each of the two prime factors, combined 2 × 2 ways through CRT.

What does NOT work

- Using the `pow(a, (p+1)//4, p)` shortcut when `p ≡ 1 (mod 4)`. This is the trap: the shortcut formula is only valid because (p+1)/4 is an integer AND algebraically produces a root *specifically* when p ≡ 3 (mod 4). Apply it to a prime where p ≡ 1 (mod 4) and it does not raise an error — it just returns a number that is not a square root of a. There's no exception to catch; you get a plausible-looking wrong value and waste time debugging downstream instead of the root cause. Always check p % 4 before picking a method, never assume the fast path applies. - Skipping the residue check and running the full algorithm on a non-residue. If (a/p) = -1, no root exists by definition, and the algorithm's loop invariants (built on t eventually collapsing to 1) assume one does. A guarded implementation raises immediately; an unguarded one (e.g. one you adapted by stripping out "unnecessary" checks to save lines) can loop, throw an unrelated exception deep in the reduction step, or return garbage. The Legendre check is one cheap exponentiation — never remove it to "simplify" the code. - Running Tonelli-Shanks directly on a composite or unfactored modulus. The whole algorithm operates inside the multiplicative structure of the field GF(p) — the 2-power order-splitting trick only holds because p is prime. Feed it a composite n and the loop either fails outright or produces a value that is not actually a square root mod n. Factor first; there is no shortcut that avoids this. - Treating a `+1` Jacobi symbol on a composite modulus as license to run Tonelli-Shanks-style reasoning. The Jacobi symbol generalizes Legendre's *computation* to composite odd moduli, but +1 does not mean a root exists — see Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus. Don't let a Jacobi +1 substitute for the factor-then-CRT path above. - Reporting the first root the algorithm returns without checking which of the `±x` pair actually matches the challenge's implicit constraint. This is the single most common way a technically-correct Tonelli-Shanks call still produces a "wrong" final answer — the square-root math was right, the root-selection step afterward was skipped.

Related

Legendre Symbol — the O(log p) yes/no on square-root existence, before you touch Tonelli-Shanks Quadratic Residues — deciding if x² ≡ a (mod n) has a solution before you go looking for one Chinese Remainder Theorem — recombining residues across coprime moduli Jacobi Symbol — the factoring-free residuosity bit, and why +1 lies on a composite modulus Gaussian Integers — factoring sums of two squares in Z[i] Elliptic Curve Fundamentals — the audit that routes to the right ECC attack Finite Field Arithmetic — the GF(p^k) substrate under AES, LFSRs, and extension-field curves/DLP