POLLARD'S p-1 factoring a number through its neighbour's factors
To split a composite n, Pollard’s p−1 method gambles that some prime factor p has a p−1 built only from small primes. Then a = 2 raised to a big smooth exponent, mod n, satisfies a ≡ 1 mod p — so gcd(a−1, n) quietly hands you p. It is Fermat’s little theorem turned into a crowbar.
THE TECHNIQUE a smooth exponent, then a gcd
Pick a base a (say 2) and a smoothness bound B. Raise a to M = lcm(1..B) modulo n. If some prime p | n has p−1 dividing M (i.e. p−1 is B-smooth), then by Fermat aM ≡ 1 mod p, so p divides aM−1 and gcd(aM−1, n) reveals it. Raise the bound to watch a factor appear. live demo
HISTORY & CREDIT two Pollard methods, endlessly confused
“Pollard’s method factors by cycle-finding” — that is p−1 rho (1975). p−1 (1974) is a different idea: smoothness, not cycles. cited
pre-1974 · exploiting the factorization of p−1 was already standard in primality testing (Pocklington, Lucas) — the insight is older than Pollard; the factoring algorithm is his. 1974 · John Pollard publishes p−1 — and its two-stage (large-prime continuation) form is already in this original paper, not a later add-on. 1975 · Pollard publishes rho (cycle-finding via Floyd, dart 040) — same author, different method, different year. The eternal mix-up. 1985 · Hendrik Lenstra’s ECM is literally p−1 generalized — swap the group (Z/pZ)* for an elliptic curve whose order you can re-roll; Williams’ p+1 (1982) is the sibling.
Stage 2 is often mis-credited to Montgomery — he sped it up (1987), Pollard already had it. Pollard 1974 (not rho)
RECOMMEND FOR I-13 modexp plus gcd, both already landed
The method is exactly two things the campaign already runs — modular exponentiation and Euclid’s gcd — so it factors on the real compiler:
$ i13 run pollard.i13 # n=1927, a=2, M=120
a = 2^120 mod 1927 = 1395 ; gcd(1394, 1927) = 41 -> 1927 = 41 x 47
Recommend:nothing new — self-referential: modexp (darts 032 / 035 / 050) and the Euclidean gcd (027, std/gcd.i13) both landed already, and together they split 1927 into 41 × 47 above (41−1 = 40 is 5-smooth and divides 120; 47−1 = 46 is not, so only 41 emerges). With bignum, the same code scales past f64’s ceiling. Note: a third dart whose payoff is a prior addition compounding — two landed features, no new primitive, a real factorization out the other end.