Tonelli-Shanks — Modular Square Root

Solve x² ≡ n (mod p): Euler-criterion check → p−1 = Q·2^S decomposition → order-reduction tweak loop converging to a root.

Euler: O(log p) p≡3 mod4: O(log p) Tonelli loop: O(S² log p) two roots: x, p−x

n = p =

Slow Fast

1 · Euler's Criterion — does a root exist?

n^(p−1)/2 = 10⁶ mod p = ?

+1 → quadratic residue (root exists)

⇄

−1 → non-residue (no root)

2 · Decompose p − 1 = Q · 2^S — peel off factors of two

p − 1 = 12 → Q (odd) = ?, S = ?

3 · Order-Reduction Tweak Loop — drive t to 1

var	meaning	value
M	current 2-group exponent	—
c	generator z^Q (order 2^S)	—
t	"error" → must reach 1	—
R	running root guess	—

order of t (2-adic) — collapses to 1:

ord(t)=?

generator c error t root R odd Q 2-part

Press Start to begin.

Explanation

Enter n and p (p an odd prime), then press Start. Try n=10, p=13 (works) or n=5, p=13 (no root) or n=2, p=7 (easy p≡3 mod 4 case).

Complexity

step	cost
Euler's criterion	O(log p)
p≡3 (mod 4) shortcut	O(log p)
find non-residue z	O(log p)
Tonelli-Shanks loop	O(S² · log p)
brute force (try all x)	O(p · log p)

Operation Log