THE FOLD / GRIND / THE MAINFRAME / THE TONELLI-SHANKS
THE TONELLI-SHANKS
the square root modulo a prime
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Tonelli–Shanks algorithm computes a square root modulo a prime — given n and prime p, it finds r with r2 ≡ n (mod p), whenever one exists. It first tests whether n is a quadratic residue (via the Legendre symbol); if p ≡ 3 (mod 4) the root is just n(p+1)/4, and otherwise it runs a clever loop that walks down the 2-adic tower of p−1 using a known non-residue. It underpins elliptic-curve point decompression and Rabin cryptography.
LIT verified live: over every prime below 2000 and every residue, the returned r satisfies r2 ≡ n, and null is returned exactly for non-residues (window.__tonelli). FIG no framing; exact.
LIT verified live: over every prime below 2000 and every residue, the returned r satisfies r2 ≡ n, and null is returned exactly for non-residues (window.__tonelli). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the heavy modular arithmetic a mainframe grinds, here inverting a square modulo a prime. Tonelli–Shanks is that inversion. AVAN (AI) built the instrument: the Legendre-symbol residue test, the 2-adic descent loop, and the r2 ≡ n verification.
Credit as content: Alberto Tonelli (1891) & Daniel Shanks (1973). The weave: David names the mainframe; I test residuosity, descend the 2-adic tower with a non-residue, and confirm the recovered root squares back to n modulo p.
Credit as content: Alberto Tonelli (1891) & Daniel Shanks (1973). The weave: David names the mainframe; I test residuosity, descend the 2-adic tower with a non-residue, and confirm the recovered root squares back to n modulo p.
3 ONE DIMENSION
Half the nonzero residues mod p are squares (quadratic residues). Tonelli–Shanks finds the pre-image: given a square n, which r squared to it? For p ≡ 3 (mod 4) it is simply n(p+1)/4.
4 TWO DIMENSIONS · INTERACTIVE
A prime p and residue n; the modular square root r is shown, with r2 mod p checked back against n.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the residues r, −r whose square is n.
AVAN’s addition (the inverse-companion): invert squaring modulo a prime — test that n is a quadratic residue, then descend the 2-adic tower of p−1 using a known non-residue to peel the root out. The inverse of ‘square r to get n mod p’ is ‘given n, recover the r that squared to it.’ Magenta is the non-residues that have no square root; green is the residue whose square is n. A square root in a finite field.
LIT Genuine Tonelli-Shanks modular square root (Tonelli 1891; Shanks 1973). Verified live: for every prime p<2000 and every residue n, when n is a quadratic residue the returned r satisfies r^2 = n (mod p), and the algorithm returns null exactly for non-residues (window.__tonelli.roots && .detectsNonResidue); sqrt(2) mod 113 = 62.
FIG No framing: the Legendre-symbol residue test, the 2-adic descent loop, and the r^2 = n verification run in-browser over 138k residue cases and hold. The AVAN inverse is honest — testing residuosity then descending the 2-adic tower with a non-residue inverts squaring modulo a prime; magenta is the non-residues with no square root, green the residue whose square is n. A square root in a finite field.
FIG No framing: the Legendre-symbol residue test, the 2-adic descent loop, and the r^2 = n verification run in-browser over 138k residue cases and hold. The AVAN inverse is honest — testing residuosity then descending the 2-adic tower with a non-residue inverts squaring modulo a prime; magenta is the non-residues with no square root, green the residue whose square is n. A square root in a finite field.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MAINFRAME · David Lee Wise (ROOT0), with AVAN