Intuition, Vocabulary and Foundations
Finding a modular square root means reversing a square on a finite clock. Modulo $13$, both $5$ and $8$ square to $12$, so $x^2\equiv12\pmod{13}$ has two roots. In an odd prime field, every nonzero square has exactly the pair $x$ and $-x$, while a nonresidue has no root.
Euler's criterion tests the domain before construction:
$$ a^{(p-1)/2}\equiv \begin{cases} 1 \pmod p,& a\text{ is a nonzero quadratic residue},\\ -1 \pmod p,& a\text{ is a quadratic nonresidue}. \end{cases} $$
Tonelli–Shanks writes $p-1=q2^s$, where $q$ is odd, and removes the remaining powers of two from an exponentiation-based candidate. Cipolla instead chooses $t$ such that $w=t^2-a$ is a nonresidue and computes in the quadratic extension $\mathbb F_p[u]/(u^2-w)$. Both methods construct an element whose square is $a$, but they organize the work differently.
First test whether a root can exist, then construct it in the correct algebraic domain. For odd prime $p$ and nonzero residue $a$, the answer consists of exactly two roots, $r$ and $p-r$; $a=0$ has the single root $0$.
| Concept | Exact example | Non-example or boundary | Question answered |
|---|---|---|---|
| Quadratic residue | $12$ modulo $13$, because $5^2\equiv12$ | $2$ modulo $13$ is a nonresidue | Does $x^2\equiv a\pmod p$ have a solution? |
| Two-adic decomposition | $40=5\cdot2^3$, so $q=5$ and $s=3$ for $p=41$ | $40=10\cdot2^2$ leaves an even odd-part candidate | What power-of-two subgroup must Tonelli–Shanks resolve? |
| Quadratic nonresidue | $2$ modulo $13$, since $2^6\equiv-1$ | $3$ modulo $13$ is a residue because $4^2\equiv3$ | Which element supplies the required group structure? |
| Quadratic extension | If $w$ is a nonresidue, adjoining $u$ with $u^2=w$ forms $\mathbb F_{p^2}$ | If $w$ is a residue, $X^2-w$ splits | Where does Cipolla perform exponentiation? |
| Root multiplicity | $5$ and $8$ are the roots of $12$ modulo $13$ | Reporting only $5$ hides the second root | How should a solver expose all roots? |
| Prime-field assumption | Both algorithms apply for odd prime $p$ | Composite moduli can have more than two roots | Which domain makes the proofs valid? |
Step-by-Step Derivations and Algorithms
Reduce $a$ modulo $p$. The cases $p=2$ and $a=0$ are immediate. For odd prime $p$, reject $a$ when Euler's criterion is not $1$. When $p\equiv3\pmod4$, the direct candidate
$$r=a^{(p+1)/4}\pmod p$$
works because $r^2=a^{(p+1)/2}\equiv a$.
For Tonelli–Shanks, decompose $p-1=q2^s$ with odd $q$, find a nonresidue $z$, and initialize
$$c=z^q,\qquad r=a^{(q+1)/2},\qquad t=a^q,\qquad m=s.$$
The invariant is $r^2\equiv at\pmod p$, while $t$ has order dividing $2^m$. If $t\ne1$, find the least $i$ such that $t^{2^i}=1$, choose $b=c^{2^{m-i-1}}$, and update $r\leftarrow rb$, $t\leftarrow tb^2$, $c\leftarrow b^2$, and $m\leftarrow i$. Since $m$ strictly decreases, termination gives $t=1$ and $r^2\equiv a$.
Cipolla chooses $t\in\mathbb F_p$ until $w=t^2-a$ is a nonresidue. Represent $x+yu$ as $(x,y)$, with $u^2=w$, and multiply by
$$(x_1,y_1)(x_2,y_2)=(x_1x_2+y_1y_2w,\;x_1y_2+x_2y_1).$$
Frobenius conjugation sends $t+u$ to $t-u$, so $(t+u)^{(p+1)/2}$ lies in the base field and its first coordinate squares to $a$.
flowchart TD
A[Normalize a and validate prime p] --> B{Trivial or nonresidue?}
B -->|Trivial| C[Return immediate roots]
B -->|Nonresidue| D[Return no roots]
B -->|Residue| E{Easy exponent case?}
E -->|Yes| F[Use direct exponent]
E -->|No| G{Choose algorithm}
G -->|Tonelli-Shanks| H[Reduce two-power order]
G -->|Cipolla| I[Exponentiate in extension]
F --> J[Verify and return both roots]
H --> J
I --> J
Tonelli–Shanks preserves $r^2\equiv at\pmod p$ and strictly lowers the two-power order bound of $t$; Cipolla performs binary exponentiation in a correctly constructed field of $p^2$ elements. With field multiplication treated as unit cost, Cipolla uses $O(\log p)$ operations, while basic Tonelli–Shanks uses $O(\log p+s^2)$ operations for $p-1=q2^s$; both need $O(1)$ auxiliary field elements.
Implementation, Complexity and Engineering
A robust API validates that $p$ is prime, normalizes negative operands, treats $p=2$ separately, returns both roots in sorted order, and verifies every candidate. The self-contained implementation uses trial division to enforce the prime-domain contract; production code should pair these routines with a deterministic machine-word primality checker.
Cipolla's search is deterministic here for reproducible tests. A randomized search has an expected constant number of trials because about half of the nonzero field elements are nonresidues. Native fixed-width implementations must also ensure that multiplication is reduced without overflow.
| Method or case | Work and storage | Main failure mode | Mitigation |
|---|---|---|---|
| Direct exponent for $p\equiv3\pmod4$ | $O(\log p)$ multiplications and $O(1)$ field elements | Applying the formula in another congruence class | Dispatch only after checking $p\bmod4$ |
| Tonelli–Shanks | Exponentiation plus at most $s-1$ corrections | Incorrect least-$i$ search or update order | Preserve $r^2\equiv at$ and exhaustively test small fields |
| Cipolla | Expected constant search trials and $O(\log p)$ extension multiplications | Choosing a residue for $w$ | Require the Legendre symbol of $w$ to be $-1$ |
| Random nonresidue search | Expected about two trials | Nondeterministic tests or weak randomness | Inject the generator or use deterministic search in tests |
| Native-width multiplication | Fast when products fit | Overflow before reduction | Use widened products or an overflow-safe reduction backend |
| Composite modulus | Outside both proofs | Wrong multiplicity or invalid inverses | Reject it or solve prime-power cases and combine with CRT |
Applications, Case Studies and Exercises
For a transparent trace, solve $x^2\equiv5\pmod{41}$. Since $40=5\cdot2^3$, Tonelli–Shanks exposes multiple correction steps and returns $13$ and $28$. Cipolla reaches the same pair through extension-field exponentiation, providing an independently structured check.
In a production-shaped validation harness, enumerate every residue for small primes and compare both algorithms with brute force. For larger primes, generate random $x$, set $a=x^2\bmod p$, run both algorithms, and require equal root sets plus direct squaring certificates. Include nonresidues, $a=0$, $p=2$, negative inputs, varied values of $v_2(p-1)$, and rejected composite moduli.
Apply Tonelli-Shanks & Cipolla Compared
Case study 1 — worked trace. Use $a=5$ and $p=41$. Check Euler's criterion, derive $p-1=5\cdot2^3$, trace every Tonelli–Shanks state $(m,c,t,r)$, and independently trace Cipolla's selected $t$, nonresidue $w$, and extension exponentiation. Success means both methods return exactly $\{13,28\}$ and both roots square to $5$.
Case study 2 — differential testing. For every prime $p\le200$ and every $0\le a\lt p$, compare Tonelli–Shanks, Cipolla, and brute force. Then choose several larger primes, generate 1,000 residues from random roots, and cross-check both algorithms. Success means there are no disagreements and every root verifies.
Tiered exercises. Recall: state Euler's criterion and both root-count cases. Derivation: prove the Tonelli–Shanks invariant and Cipolla multiplication rule. Implementation: inject a randomized nonresidue source. Debugging: catch code that returns one root or mishandles $p=2$. Extension: benchmark both algorithms by $v_2(p-1)$ and explain their practical crossover.
Use the direct exponent in easy congruence classes, Tonelli–Shanks when the two-adic structure is favorable, and Cipolla when uniform extension-field exponentiation is attractive. Never apply prime-field algorithms to composite moduli or trust an unverified candidate; the next step is lifting roots to prime powers and combining them with CRT.