Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

How to Learn Tonelli–Shanks: Quadratic Residues, Modular Square Roots, Euler’s Criterion and Finite-Field Reasoning

Quick Read: Tonelli–Shanks solves a deceptively simple problem: given an odd prime p and a number n, find x such that x² ≡ n (mod p), when such a square root exists. Learning it well develops modular arithmetic, proof technique, loop invariants, finite-group reasoning and implementation discipline.

Start with the ordinary square root

Over the real numbers, asking for a square root feels familiar: 5² = 25, so 5 is a square root of 25. Modular arithmetic changes the question. Working modulo 13, for example, 5² = 25 ≡ 12 (mod 13). The number line has wrapped into a finite system.

Now the task is not “which real number squares to n?” It is “which residue class squares to n after reduction modulo p?” This shift in representation is the first conceptual hurdle.

The first vocabulary: quadratic residues

A non-zero value n is a quadratic residue modulo p if there exists some x for which x² ≡ n (mod p). If no such x exists, n is a quadratic non-residue.

For a small prime, you can build understanding by brute force. Modulo 11:

1² ≡ 1
2² ≡ 4
3² ≡ 9
4² ≡ 5
5² ≡ 3
6² ≡ 3
7² ≡ 5
8² ≡ 9
9² ≡ 4
10² ≡ 1   (mod 11)

The non-zero quadratic residues are therefore 1, 3, 4, 5 and 9. Notice the symmetry: if x is a square root, then p-x is the other square root.

Euler’s criterion: test before solving

Before Tonelli–Shanks tries to construct a square root, it needs to know whether one exists. Euler’s criterion gives a remarkably compact test. For an odd prime p and non-zero n:

n^((p-1)/2) ≡  1 (mod p)  if n is a quadratic residue
n^((p-1)/2) ≡ -1 (mod p)  if n is a non-residue

This is a good place to stop and ask a learner to predict results for several small primes before running code. The purpose is not merely verification; it is to build an intuition that exponentiation can reveal algebraic structure.

The easy special case: p ≡ 3 mod 4

When p ≡ 3 (mod 4), modular square roots are especially convenient. If n is a quadratic residue, then:

x ≡ n^((p+1)/4) (mod p)

A professional implementation should exploit this case because it is simpler and fast. Tonelli–Shanks is needed for the general odd-prime case.

The structural move: factor p − 1

Tonelli–Shanks begins by writing:

p - 1 = Q · 2^S

where Q is odd. This is not arbitrary bookkeeping. The algorithm isolates the power-of-two part of the multiplicative group size. The difficult part of the square-root problem is then corrected step by step through powers of two.

To find Q and S in code, repeatedly divide p-1 by 2 until the remaining value is odd.

Find a quadratic non-residue

The algorithm also needs a value z that is known not to be a square modulo p. Euler’s criterion can find one: test z = 2, 3, 4, … until z^((p-1)/2) ≡ -1 (mod p).

For large cryptographic code, selection and timing require more care, but for learning and general-purpose algorithm work, this search makes the logic transparent.

The state variables

A standard presentation keeps four important quantities:

M — the current power-of-two exponent.
c — a power of the chosen non-residue.
t — a value that measures how far the candidate is from being a true square root.
R — the current square-root candidate.

One common initialization is:

M = S
c = z^Q mod p
t = n^Q mod p
R = n^((Q+1)/2) mod p

What is the loop trying to achieve?

The loop continues until t = 1. When that happens, the maintained relationship implies that R² ≡ n (mod p), so R is a square root.

If t is not 1, the algorithm finds the smallest i for which:

t^(2^i) ≡ 1 (mod p)

That i tells us how far down the power-of-two chain we must move. A carefully selected correction factor b then updates R, t and c so that the order of t decreases. The algorithm makes measurable progress instead of guessing.

Reference pseudocode

tonelli_shanks(n, p):
    n = n mod p
    if n == 0: return 0
    if legendre(n, p) != 1: return NO_ROOT
    if p mod 4 == 3:
        return powmod(n, (p + 1) / 4, p)

    Q = p - 1
    S = 0
    while Q is even:
        Q /= 2
        S += 1

    find z with legendre(z, p) == -1

    M = S
    c = powmod(z, Q, p)
    t = powmod(n, Q, p)
    R = powmod(n, (Q + 1) / 2, p)

    while t != 1:
        find smallest i in [1, M) such that t^(2^i) == 1 mod p
        b = c^(2^(M-i-1)) mod p
        R = R * b mod p
        t = t * b * b mod p
        c = b * b mod p
        M = i

    return R

A small worked example

Find a square root of 10 modulo 13. First, 13 is prime and 10 is a quadratic residue. Factor 12 = 3 · 2², so Q = 3 and S = 2. A suitable non-residue is 2. The algorithm initializes its state, then performs the correction loop until t becomes 1. One answer is 6 because 6² = 36 ≡ 10 (mod 13). The other root is 13 - 6 = 7.

When learning, do this example by hand before coding it. The goal is to see how the abstract state variables move, not to rush past them.

Correctness: the invariant matters more than the code

A useful invariant is that the candidate R and correction term t stay related by R² ≡ n·t (mod p). The updates preserve that relationship. Meanwhile, the algorithm reduces the relevant power-of-two order of t. Eventually t becomes 1, leaving R² ≡ n.

This is a model lesson in advanced algorithms: a short program may hide a proof with several moving parts. Professional understanding means being able to state what each variable represents and why each update preserves correctness.

Complexity

The cost is dominated by modular exponentiation and the power-of-two correction loop. Exact complexity descriptions depend on the arithmetic model and implementation. For algorithm learners, the important point is that fast exponentiation makes the necessary powers efficient, while the factorization of p-1 determines how many correction stages are needed.

Implementation mistakes that matter

Forgetting that the method assumes an odd prime modulus.
Failing to test whether n is a quadratic residue before entering the loop.
Using ordinary exponentiation instead of modular exponentiation.
Overflowing machine integers before applying the modulus.
Finding i incorrectly by not repeatedly squaring t.
Forgetting the simple p mod 4 = 3 shortcut.
Returning one root and not recognising that p-R is the second root.

Professional implementation concerns

In cryptographic software, mathematical correctness is only one requirement. Timing behaviour, side channels, constant-time operations, validated finite-field routines and carefully selected parameters also matter. A textbook Tonelli–Shanks implementation should therefore not be copied directly into security-critical production code.

The professional lesson is broader: an algorithm can be mathematically correct yet operationally unsafe in a hostile environment.

How Tonelli–Shanks connects to bigger ideas

Fast modular exponentiation: the engine behind Euler’s criterion and the state initialization.
Group structure: the non-zero residues modulo a prime form a multiplicative group.
Orders of elements: repeated squaring tracks the power-of-two component of an element’s order.
Finite fields: modular square roots are one instance of algebraic computation over finite structures.
Cryptography: finite-field square roots appear in elliptic-curve and hashing constructions, although production implementations require specialist care.

A practice ladder from beginner to professional

Beginner: list all quadratic residues for primes 7, 11 and 13.
Foundation: implement modular exponentiation by repeated squaring.
Intermediate: implement Euler’s criterion and test it exhaustively for small primes.
Intermediate: implement the p ≡ 3 mod 4 shortcut.
Advanced: implement Tonelli–Shanks and compare every result with brute force for small primes.
Professional: test large primes, measure iterations as the 2-adic factor of p-1 changes, and document assumptions explicitly.

How to debug your implementation

Do not debug by staring at the final root. Print the state tuple (M, c, t, R) at every iteration. Check the invariant R² ≡ n·t (mod p). Check that M decreases. Check that t eventually becomes 1. When a sophisticated algorithm fails, inspect the invariant rather than only the output.

The final idea

Tonelli–Shanks is worth learning not because modular square roots appear in every program, but because it trains a powerful form of algorithmic thinking: expose hidden algebraic structure, maintain a precise invariant, make guaranteed progress and turn a proof into executable computation.