Pollard's p-1 Factorization — when a prime's predecessor is smooth

Factors n = p*q when one prime factor p was generated so that p-1 is B-smooth (all its prime power factors are below a bound B): Fermat's little theorem gives a^(k*(p-1)) ≡ 1 mod p for any multiple k*(p-1), so gcd(a^M - 1, n) reveals p once M absorbs p-1 as a factor.

The signal that gives it away

There is no visible artifact in the ciphertext or public key that screams "smooth p-1" the way small-e or common-modulus challenges announce themselves — you cannot see it by inspecting n alone. The signal is contextual:

- The challenge narrative hints at weak prime generation: primes described as "randomly generated" via a naive routine, or explicitly said to be picked from a restricted/structured process, or generated with unusually small bit-length building blocks. - Trial division and Fermat factorization (fermat-factorization) have already failed — so the primes are not obviously close and not obviously small-factor in the trivial sense. - Small-to-medium Pollard rho (pollard-rho-factorization) also fails or is too slow — ruling out "one factor is just small." - At that point, smooth-p-1 is a cheap blind probe, not something you can confirm in advance from the public key. You run it because it's cheap, not because you proved it will work. - Williams' p+1 method is the structural dual (smooth p+1 instead of p-1) — if p-1 fails but you still suspect structured prime generation, that is the next probe.

How to exploit it

1. Pick a base a = 2 (coprime to n; almost always fine since n is odd). 2. Raise a to successive prime-power exponents up to a bound B, taking a gcd with n periodically (or once at the end):

```python from math import gcd from sympy import primerange

def pm1(n, B=10**6, a=2): for p in primerange(2, B): pe = p while pe <= B: a = pow(a, p, n) pe *= p d = gcd(a - 1, n) if 1 < d < n: return d return None ```

3. Read the gcd result and adjust — this is the operational core, the part that saves time versus blindly re-running with a bigger bound each time: - gcd == 1: M has not yet absorbed p-1 as a factor. Raise `B` and retry — you have not failed, you have not gone far enough yet. - 1 < gcd < n: success, gcd is p (or a nontrivial factor). Recover the cofactor n/p and derive the RSA private key via rsa-fundamentals. - gcd == n: you overshot — M now absorbs structure from *both* primes' predecessors (or a has unexpectedly small order mod n). Lower `B`, or switch to a different base a, and retry. 4. B = 10^6 is a reasonable default starting bound for a first probe in a CTF setting — cheap enough to run in seconds, large enough to catch primes deliberately built from small factors. Escalate from there only if the challenge context still points at structured/smooth prime generation. 5. For a stronger and more general attack on the same idea (smooth-ish medium factors without needing the *whole* of p-1 to be smooth), the elliptic-curve method (ECM) generalizes this approach and is the standard escalation: ecm.factor(n) in SageMath. Reach for ECM once the plain p-1 probe with a reasonable B comes back empty.

Related

Integer Factorization Methodology — which factoring attack to try, in what order Pollard's Rho Factorization — finding a small-to-medium factor when trial division and Fermat fail Fermat Factorization — recovering p, q when the RSA primes were chosen too close RSA Fundamentals — the routing hub: which artifact points to which attack Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't)

What does not work

- Treating it as a default first move. It is a targeted probe for a specific weakness (structured prime generation), not a general factoring method. If nothing in the challenge suggests deliberately weak primes, trial division, Fermat, and Pollard rho are cheaper and more broadly applicable first steps — try those first via integer-factorization-methodology. - Assuming a `gcd == n` result means the method is wrong for this `n`. It usually just means the bound B was too large and absorbed structure from the *other* prime too, or the base was unlucky. Lower B or change a before giving up. - Giving up after one bound. A single failed run at a small B (gcd == 1) tells you nothing definitive — it only means p-1's largest prime factor exceeds that B. Raising B is cheap up to a point; only abandon the approach once B is large enough that the runtime (O(B log B log^2 n)) stops being cheap relative to just trying rho or ECM instead. - Expecting it to work on well-generated RSA primes. Modern key-generation libraries reject primes with smooth p-1 specifically because of this attack; it only bites intentionally or accidentally weak generation (toy/demo key generators, homegrown "random prime" routines, CTF-crafted keys).