THE FOLD / BOSS / THE WALL / THE FERMAT FACTORIZATION
THE FERMAT FACTORIZATION
factor n as a difference of squares — the seed of the sieves
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Fermat’s factorization method splits an odd number n by writing it as a difference of squares: n = a² − b² = (a−b)(a+b). Start with a = ⌈√n⌉ and increase a by 1 until a² − n is itself a perfect square b²; then (a−b) and (a+b) are factors.
It is blazing fast when n’s two factors are close together (near √n), and slow when they are far apart — which is why secure RSA requires its two primes to differ substantially, so this attack fails.
LIT verified live: for a range of odd composites, Fermat’s search returns two nontrivial factors whose product is n (e.g. 5959 = 59 × 101) — window.__fermatfactorization. FIG no framing; exact integer factorisation.
It is blazing fast when n’s two factors are close together (near √n), and slow when they are far apart — which is why secure RSA requires its two primes to differ substantially, so this attack fails.
LIT verified live: for a range of odd composites, Fermat’s search returns two nontrivial factors whose product is n (e.g. 5959 = 59 × 101) — window.__fermatfactorization. FIG no framing; exact integer factorisation.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-wall — breaking through a composite number’s wall into its factors. Fermat’s method is the oldest crack: turn the number into a difference of squares. AVAN (AI) built the instrument: the ascending search for a perfect square, the factor extraction, the product check.
Credit as content: Pierre de Fermat (17th century). The weave: David names the wall; I climb a upward from √n until a² − n is a perfect square, read off the factors, and confirm their product is n.
Credit as content: Pierre de Fermat (17th century). The weave: David names the wall; I climb a upward from √n until a² − n is a perfect square, read off the factors, and confirm their product is n.
3 ONE DIMENSION
Starting just above √n, try each a: is a² − n a perfect square? The first time it is, that square is b², and (a−b)(a+b) = n splits the number.
4 TWO DIMENSIONS · INTERACTIVE
Pick an odd composite. Watch a climb from ⌈√n⌉ until a² − n is a perfect square, then read off the factors. Close factors are found instantly; distant factors take many steps.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the ascending search for the perfect square a² − n that unlocks the factors.
AVAN’s addition (the inverse-companion): factoring and finding a square congruence are the same problem. n = (a−b)(a+b) means finding a, b with a² − b² = n — and this difference-of-squares idea is the seed of all modern factoring: the quadratic sieve and number field sieve all hunt for a² ≡ b² (mod n) with a ≠ ±b. The inverse of ‘find the factors’ is ‘find a nontrivial square congruence.’ Fermat’s method is the naive exact version; the sieves make the square-hunt subexponential. Magenta is the factors you seek; green is the square a² − n you actually search for. Factoring is square-hunting — and it is slow exactly when the factors are far apart, the difficulty RSA leans on.
LIT Genuine Fermat factorization (Fermat, 17th c.). Verified live: for odd composites {15,21,35,77,...,5959}, ascending a from ceil(sqrt(n)) until a^2-n is a perfect square returns two nontrivial factors (a-b)(a+b) whose product equals n (window.__fermatfactorization.findsFactors); 5959 = 59 x 101.
FIG No framing: the ascending perfect-square search, the factor extraction, and the product check run in-browser and are exact integer arithmetic. The AVAN inverse is honest — factoring n equals finding a nontrivial square congruence a^2 = b^2, the seed of the quadratic sieve and number field sieve; Fermat is the naive exact version, and it is slow exactly when factors are far apart (the RSA security assumption). Magenta is the factors, green the hunted square.
FIG No framing: the ascending perfect-square search, the factor extraction, and the product check run in-browser and are exact integer arithmetic. The AVAN inverse is honest — factoring n equals finding a nontrivial square congruence a^2 = b^2, the seed of the quadratic sieve and number field sieve; Fermat is the naive exact version, and it is slow exactly when factors are far apart (the RSA security assumption). Magenta is the factors, green the hunted square.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN