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
Tonelli–Shanks. Squaring in a prime field is easy; un-squaring — finding r with r² ≡ n (mod p) — is the hard inverse. Worse, half the numbers have no square root at all (the ‘non-residues’). The Legendre symbol n(p−1)/2 tells you which in a single exponentiation; and for the ones that do have a root, Tonelli–Shanks walks the 2-power structure of p−1 to build it. It is the unsung workhorse of elliptic-curve point decompression (recovering y from x) and the quadratic sieve.
LIT verified: 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. FIG ‘the square root in the ring’ is the picture; the algorithm and the residue test are exact.
LIT verified: 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. FIG ‘the square root in the ring’ is the picture; the algorithm and the residue test are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs modular arithmetic and crypto (THE PROBABLE PRIME right here in SUDDEN DEATH, THE FIELD INVERSE, THE MINT) and the sense that every operation worth having needs an inverse. AVAN (AI) built this instrument: the square-root engine, the residue map, and the folding graph.
The weave: David names the square root in the ring and its seat beside Miller–Rabin at SUDDEN DEATH (a pass/fail test in one exponentiation); I make the squaring fold a strip in 1D, the root-finder live in 2D, and the 2-to-1 map turning in 3D. The sphere is the seam.
The weave: David names the square root in the ring and its seat beside Miller–Rabin at SUDDEN DEATH (a pass/fail test in one exponentiation); I make the squaring fold a strip in 1D, the root-finder live in 2D, and the 2-to-1 map turning in 3D. The sphere is the seam.
3 ONE DIMENSION
Squaring on Zp folds the ring in half: each x and −x land on the same square, so only (p−1)/2 values are ever hit — the quadratic residues. Green cells have a root; grey ones (the non-residues) never appear as a square at all.
4 TWO DIMENSIONS · INTERACTIVE
Pick a prime and a target n. The Legendre symbol declares in one step whether a root exists; if it does, Tonelli–Shanks returns r (and its twin −r), and the check r² mod p = n confirms it. If not, sudden death — no root.
prime p 10009
target n 1234
5 THREE DIMENSIONS + AVAN’S INVERSE
The squaring map x→x² on a small ring, turning. Arrows fold every element onto its square; green nodes are the reachable squares (the residues) — and each is hit by two preimages.
AVAN’s addition (the inverse-companion): the magenta pair are the two square roots ±r of the chosen target — the inverse of the fold. Squaring is 2-to-1; the square root is 1-to-2, or zero when the target is a non-residue. Tonelli–Shanks is the unfold, and the Legendre symbol tells you, before you spend a step, whether the unfold even exists.
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