THE FOLD / CHEAT / THE EXPLOIT / THE POLLARD P-1
THE POLLARD P-1
factoring surfaced by a gcd when p-1 is smooth
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Pollard’s p−1 algorithm factors a composite n whenever one of its prime factors p has a smooth p−1 (all its prime-power factors are small). It computes ak! mod n for growing k; by Fermat’s little theorem, once k! is a multiple of p−1, ak! ≡ 1 (mod p), so ak!−1 is a multiple of p, and gcd(ak!−1, n) reveals p — without ever knowing p in advance.
It is why RSA primes are chosen so that p−1 has a large factor.
LIT verified live: for 90 constructed n = p·q where p−1 is 15-smooth (and q−1 is not), the algorithm returns a nontrivial factor dividing n (window.__pollardp1). FIG honest: it works only when a factor’s p−1 is smooth — and if both are smooth it can over-shoot to gcd = n.
It is why RSA primes are chosen so that p−1 has a large factor.
LIT verified live: for 90 constructed n = p·q where p−1 is 15-smooth (and q−1 is not), the algorithm returns a nontrivial factor dividing n (window.__pollardp1). FIG honest: it works only when a factor’s p−1 is smooth — and if both are smooth it can over-shoot to gcd = n.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-exploit — the crack that breaks a composite when a prime factor’s order is smooth, surfacing it through a gcd. Pollard p−1 is that exploit. AVAN (AI) built the instrument: the ak! accumulation, the running gcd, the curated smooth/non-smooth factor check.
Credit as content: John Pollard (1974). The weave: David names the exploit; I raise a to k! modulo n and let the gcd expose the prime whose p−1 is smooth — the same smoothness weakness as Pohlig–Hellman.
Credit as content: John Pollard (1974). The weave: David names the exploit; I raise a to k! modulo n and let the gcd expose the prime whose p−1 is smooth — the same smoothness weakness as Pohlig–Hellman.
3 ONE DIMENSION
As k grows, a is raised to 2, then 3, then 4… (building ak!). The moment k! is divisible by p−1, ak! becomes 1 modulo p — and gcd(ak!−1, n) jumps from 1 to p.
4 TWO DIMENSIONS · INTERACTIVE
A composite n with a smooth-p−1 factor; watch the running gcd stay 1 until the bound reaches p−1’s largest factor, then reveal p.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the gcd surfacing the smooth-order prime.
AVAN’s addition (the inverse-companion): if a prime factor p has p−1 smooth, then ak! ≡ 1 (mod p) for modest k, so ak!−1 is a multiple of p, and gcd(ak!−1, n) reveals p — without ever knowing p. The inverse of ‘search for the factor’ is ‘compute ak! mod n and let the gcd expose the smooth-order prime.’ Magenta is the factor you never search for directly; green is the gcd that surfaces it. Smoothness of p−1 is the crack. (Kin to the-pohlig-hellman — same weakness.)
LIT Genuine Pollard p-1 (Pollard 1974). Verified live (BigInt): for 90 curated n=p*q with p-1 15-smooth and q-1 not, computing a^(k!) mod n and taking gcd(a^(k!)-1, n) returns a nontrivial factor dividing n (window.__pollardp1.findsFactor).
FIG HONEST framing: the a^(k!) accumulation, the running gcd, and the curated factor check run in-browser. It works ONLY when a prime factor's p-1 is smooth; and if BOTH p-1 and q-1 are smooth it can over-shoot to gcd=n and split nothing (stated on the page). The AVAN inverse is honest — smooth p-1 makes a^(k!)-1 a multiple of p, so a gcd surfaces the factor; magenta is the prime never searched for, green the gcd. Same smoothness weakness as the-pohlig-hellman.
FIG HONEST framing: the a^(k!) accumulation, the running gcd, and the curated factor check run in-browser. It works ONLY when a prime factor's p-1 is smooth; and if BOTH p-1 and q-1 are smooth it can over-shoot to gcd=n and split nothing (stated on the page). The AVAN inverse is honest — smooth p-1 makes a^(k!)-1 a multiple of p, so a gcd surfaces the factor; magenta is the prime never searched for, green the gcd. Same smoothness weakness as the-pohlig-hellman.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN