Fermat Factorization — recovering p, q when the RSA primes were chosen too close

Factors n = p*q by writing it as a difference of squares n = a^2 - b^2 = (a-b)(a+b) and searching a upward from ceil(sqrt(n)) — fast if and only if p and q are close together.

The signal that gives it away

- The challenge text or generator hints that the primes were picked "close", "near", "consecutive", or explicitly as p = randprime(); q = nextprime(p). - General-purpose factoring (factordb, sympy.factorint) fails outright even though n is full-size — the *only* structural weakness is a small |p - q|. That combination (full-size n, everything else fails, but the source/spec brags about "randomly generated" primes of the same bit-length) is the tell: real random primes of equal bit-length are close far more often than intuition suggests, and challenge authors sometimes make this worse by generating q as literally the next prime after p. - No oracle, no leaked bits, no small exponent — this is a pure property of how n was built, discoverable from n alone.

How to exploit it

1. Start at a = isqrt(n), bump to a+1 if a*a < n. 2. At each step test whether b2 = a*a - n is a perfect square; the moment it is, p = a - b, q = a + b.

``python from sympy import integer_nthroot a, _ = integer_nthroot(n, 2) a += 1 while True: b2 = a * a - n b, exact = integer_nthroot(b2, 2) if exact: p, q = a - b, a + b break a += 1 ``

3. Once p, q are known, derive the RSA private key directly through RSA Fundamentals — the routing hub: which artifact points to which attack (phi = (p-1)*(q-1), d = e^-1 mod phi). 4. Cost scales with the gap, not with `n`. Publicly corroborated: if the true factor differs from sqrt(n) by less than (4n)^(1/4), the loop terminates in essentially one step, independent of how large n is; more generally the number of iterations is on the order of (gap)^2 / (2*sqrt(n)). In our runs this meant primes within roughly the first ~2^20–2^24 of each other resolved in well under a second to a few seconds of pure Python; beyond that the loop cost grows quadratically with the gap and becomes impractical fast. 5. If it doesn't hit immediately, don't give up at step 1 — try the multiplier trick. For a gap that's a bit too large for plain Fermat but still suspiciously small, run the search on k*n for small integer multipliers k (2, 3, 5, ... a handful of small values) instead of n itself; this is the standard practical extension (related to Lehman's refinement, which combines Fermat with trial division to reach O(n^(1/3))) and it recovers cases that fail against n directly because scaling can turn an awkward gap into an accessible one. 6. Bound the raw loop explicitly (a few million iterations is a reasonable cutoff in a CTF time budget) so that a wrong guess about "close primes" fails fast instead of spinning for the rest of the round — if it's still not hitting after that budget, the primes are not actually close and this is the wrong attack.

What does NOT work

- Running Fermat blind on every challenge "just in case." It only pays off when the gap is genuinely small; on primes generated independently at normal RSA sizes the gap is astronomically large and the loop will never terminate in any reasonable time. Check for the signal (hint text, generator code, or at minimum "everything else about this n looks fine") before spending the time budget here. - Confusing "close primes" with "small factor." Fermat targets p and q near sqrt(n); if instead one factor is just small or medium-sized in absolute terms (regardless of how far it is from the other factor), Fermat does not help — that's the signal for Pollard's Rho Factorization — finding a small-to-medium factor when trial division and Fermat fail instead. Diagnose which situation you're in before picking the method: they look similar ("factoring failed") but the fix is opposite in what makes it fast. - Expecting it to succeed against a smooth-but-not-close `p-1`. A structurally weak prime (smooth p-1) with no proximity to q is not a Fermat case at all — that's Pollard's p-1 Factorization — when a prime's predecessor is smooth. Fermat's speed comes purely from the *arithmetic distance* between the two factors, not from any property of either factor individually. - Plain trial division as a substitute. It shares the same "only wins on special structure" limitation but for the opposite extreme (very small factors); it will not find close-but-large primes any faster than brute force. Trial division and Fermat are complementary probes, not substitutes for each other — run both cheaply before escalating to Integer Factorization Methodology — which factoring attack to try, in what order's heavier branches.

Related

RSA Fundamentals — the routing hub: which artifact points to which attack 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 Pollard's p-1 Factorization — when a prime's predecessor is smooth Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root