Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 37 · Quadratic Residues

Tonelli-Shanks Square Roots

Compute square roots modulo any odd prime with the Tonelli-Shanks algorithm, understand why it works, lift roots to prime powers, and combine them with CRT.

Knowing that x² ≡ a (mod p) has a solution is only half the story. Often you need the root itself: to decompress an elliptic-curve point, to decode a Rabin ciphertext, or to run the quadratic sieve. When p ≡ 3 (mod 4) the shortcut a^((p+1)/4) works. For p ≡ 1 (mod 4), which includes most interesting primes, we need Tonelli-Shanks (Tonelli 1891, Shanks 1973).

The algorithm is a small, elegant loop. It splits the group of units into a part of odd order, where a root is easy, and a part of 2-power order, where we repair the error step by step.

The idea

Write p - 1 = Q · 2^S with Q odd. Let a be a residue. Then a^Q lies in the subgroup of order dividing 2^(S-1), and a^((Q+1)/2) is almost a square root: its square is a · a^Q. If we call t = a^Q, the error t has a 2-power order. To cancel t, we need an element of order 2^k to multiply into the guess. Such an element comes from any non-residue z: c = z^Q has order exactly 2^S.

Python Inspecting the split p - 1 = Q * 2^S

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When S = 1 (primes 3 mod 4) the repair step is unnecessary and we get the shortcut. Primes like 65537 (S = 16) or 998244353 (S = 23) need many correction rounds.

The algorithm

  1. Find a non-residue z (try 2, 3, 5, ... and use Euler's criterion).
  2. Set M = S, c = z^Q, t = a^Q, R = a^((Q+1)/2).
  3. While t ≠ 1: find the smallest i with t^(2^i) = 1; let b = c^(2^(M-i-1)); then set M = i, c = b², t = t·b², R = R·b.
  4. Return R (and p - R).

The loop invariant is R² = a·t. Each round strictly reduces the order of t, so it ends in at most S rounds with t = 1, which gives R² = a.

Python Tonelli-Shanks

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each root is verified by squaring, and each None is confirmed to be a true non-residue. The primes 65537 and 998244353 stress the long correction loop.

Compare with the library

Python Agreement with SymPy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 255-bit prime 2^255 - 19 behind Curve25519 is handled instantly: the algorithm is polynomial in log p, with at most S loop rounds, each costing a few modular multiplications.

Prime powers: Hensel lifting

Suppose you know r² ≡ a (mod p) and want a root modulo p^k. Hensel's lemma says that for odd p not dividing a, a simple Newton step lifts it: r' = r - (r² - a)·(2r)⁻¹ (mod p²), doubling the precision each time.

Python Lifting a root from p to p^k

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed True confirms r² ≡ 10 (mod 13⁶).

Any modulus: combine with CRT

For a general modulus, factor n, take the root modulo each prime power, and combine them with the Chinese remainder theorem. Choosing the sign at every prime gives all 2^k roots. This is exactly how the Rabin cryptosystem decrypts, so it is only as hard as factoring.

Python All square roots modulo n via CRT

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 1001 there are 8 roots of 9: the combinations of ±3 modulo each of 7, 11 and 13.

flowchart TD
    A["p - 1 = Q * 2^S"] --> B["find non-residue z, c = z^Q"]
    B --> C["R = a^((Q+1)/2), t = a^Q"]
    C --> D{"t = 1?"}
    D -->|yes| E["R is a root"]
    D -->|no| F["find least i: t^(2^i) = 1"]
    F --> G["b = c^(2^(M-i-1)), update M, c, t, R"]
    G --> D

The Tonelli-Shanks loop.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In Tonelli-Shanks, what are Q and S for p = 41?

    40 = 5 * 2^3.
  2. 2. What is the loop invariant?

    Starting with R^2 = a * a^Q = a * t, every update keeps R^2 = a t, and the loop ends when t = 1.
  3. 3. Why is a non-residue z needed?

    c = z^Q generates the 2-power subgroup, so suitable powers of c cancel any error t.
  4. 4. How many square roots does 9 have modulo 1001 = 7 * 11 * 13?

    Two roots modulo each of three primes combine by CRT into 2^3 = 8 roots.

Summary

  • For p ≡ 3 (mod 4) use a^((p+1)/4); otherwise Tonelli-Shanks.
  • It writes p - 1 = Q·2^S, starts with R = a^((Q+1)/2) and corrects R using powers of z^Q until t = a^Q becomes 1.
  • Runtime is polynomial in log p; the loop runs at most S times.
  • Hensel lifting extends a root mod p to p^k; CRT combines roots mod prime powers.
  • Roots modulo a composite are as hard to find as factoring it.

Next: RSA from Scratch