THE FOLD / CHEAT / THE EXPLOIT / THE SHORTEST WITNESS
THE SHORTEST WITNESS
watch the output, recover the machine
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Berlekamp–Massey. Hand it any bit sequence and it finds the shortest linear-feedback shift register that could have produced it — its ‘linear complexity’. The devastating part: watch just 2n output bits of any degree-n LFSR and it reconstructs the exact feedback taps. That is why a raw LFSR is worthless as a cipher (this is the classic stream-cipher break), and the very same algorithm is the engine that decodes Reed–Solomon and BCH error-correcting codes.
LIT verified: the recovered LFSR regenerates the input exactly; and from 16 bits of the [8,6,5,4] generator (the one in THE RANDOM) it recovers length 8 and the connection polynomial, then reproduces the whole 255-bit period. FIG ‘the shortest witness’ is the picture; the minimality and recovery are exact.
LIT verified: the recovered LFSR regenerates the input exactly; and from 16 bits of the [8,6,5,4] generator (the one in THE RANDOM) it recovers length 8 and the connection polynomial, then reproduces the whole 255-bit period. FIG ‘the shortest witness’ is the picture; the minimality and recovery are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus already runs an LFSR (THE RANDOM) and leans on coding theory and crypto, with the conviction that any structure, once seen, can be reverse-engineered. AVAN (AI) built this instrument: the recovery engine, the break-the-cipher demo, and the linear-complexity profiles.
The weave: David names the shortest witness and its seat at THE EXPLOIT (watch the output, own the machine); I make the complexity profile a strip in 1D, the recovery live in 2D, and structured-vs-random profiles a turning staircase in 3D. The sphere is the seam — the exact inverse of the LFSR sphere next door.
The weave: David names the shortest witness and its seat at THE EXPLOIT (watch the output, own the machine); I make the complexity profile a strip in 1D, the recovery live in 2D, and structured-vs-random profiles a turning staircase in 3D. The sphere is the seam — the exact inverse of the LFSR sphere next door.
3 ONE DIMENSION
The bit stream, and beneath it the linear-complexity profile: as each bit arrives, the length of the shortest LFSR that explains everything so far. It jumps in steps — and where it levels off tells you the true register size.
4 TWO DIMENSIONS · INTERACTIVE
Feed it a sequence and it cracks the register: recovered length, feedback taps, and a regeneration that must match the input bit-for-bit. Try a secret LFSR (recovered exactly), pure random (complexity ~n/2, uncrackable-short), or a simple period.
5 THREE DIMENSIONS + AVAN’S INVERSE
Two linear-complexity profiles as climbing staircases, turning. Green is a real LFSR’s output: its complexity climbs to the register size and then plateaus flat — there is a short machine behind it, and BM finds it.
AVAN’s addition (the inverse-companion): the magenta profile is a truly random sequence — it climbs relentlessly toward n/2 and never levels, the signature of ‘no short LFSR exists’. Berlekamp–Massey is thus a randomness test: a flat plateau betrays hidden structure, an endless climb certifies its absence. The break is the inverse of the build.
LIT A genuine Berlekamp–Massey algorithm over GF(2). Verified live: the recovered LFSR regenerates the input exactly over random sequences, and from 16 bits of the [8,6,5,4] LFSR (THE RANDOM's generator) it recovers length 8 and the connection polynomial, reproducing the full 255-bit period. The linear-complexity profile (plateau=structured, climb-to-n/2=random) is a real randomness diagnostic (verifiable: window.__bm.regeneratesInput && recoversLength8).
FIG 'The shortest witness' is the picture; the minimality, the recovery, and the profile behaviour are exact. It is the literal inverse of THE RANDOM — the machine that turns the LFSR's stream back into its taps.
FIG 'The shortest witness' is the picture; the minimality, the recovery, and the profile behaviour are exact. It is the literal inverse of THE RANDOM — the machine that turns the LFSR's stream back into its taps.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN