THE FOLD / BOSS / SUDDEN DEATH / THE SQUARE ROOT IN THE RING
THE SQUARE ROOT IN THE RING
un-square in a prime field — if a root exists at all
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 A genuine Tonelli-Shanks algorithm. Verified live: for prime p and a quadratic residue n, the returned r satisfies r²≡n mod p; non-residues are correctly flagged unsolvable via the Legendre symbol — over thousands of random p, n. Squaring is exactly 2-to-1 on Z_p (each square has two roots; half the ring has none), which is the structure it inverts (verifiable: window.__tonelli.rootsCorrect && nonResiduesFlagged).
FIG 'The square root in the ring' is the picture; the algorithm, the Legendre residue test, and the 2-to-1 squaring map are exact. It really is the point-decompression step in elliptic-curve crypto.
FIG 'The square root in the ring' is the picture; the algorithm, the Legendre residue test, and the 2-to-1 squaring map are exact. It really is the point-decompression step in elliptic-curve crypto.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SUDDEN DEATH · David Lee Wise (ROOT0), with AVAN