Integer Factorization Methodology — which factoring attack to try, in what order

Factoring n = p*q (or a multiprime/prime-power n) is never one algorithm — it's a decision tree ordered from free to expensive, and picking the wrong rung first is the single biggest time sink in RSA challenges.

The signal that betrays it

Any RSA challenge that hands you n, e, c and nothing else (no huge e, no oracle, no partial leak) is implicitly asking you to factor n. The sub-signal that tells you WHICH branch of the tree to jump to:

- n is small (well under ~100 bits) or "looks reused" across challenges → try lookup first, before running anything locally. - The challenge script generates primes with nextprime(p), or the prompt/flavor text says primes are "close", "consecutive", "generated back to back" → close-primes branch. - The generator comment mentions "smooth", "weak prime", or picks p by constructing p-1 from small factors → smooth-p-1 branch. - Nothing in the source hints at structure, n just looks like a normal RSA modulus → default to the general small-to-medium-factor branch, then escalate. - gcd-based probes keep returning n itself, or the generator literally does p**k → prime-power branch, not "hard" factoring at all. - n's bit length is large (2048+) with an unremarkable prime-generation routine and no other weakness anywhere in the challenge → this is usually a sign you're not meant to factor n at all; re-read the challenge for the actual intended artifact (small/huge e, second modulus, oracle, leak).

How to exploit it

Try the branches in this order — each one is a cheap probe before you commit to the expensive one:

1. Perfect-power check first. sympy.perfect_power(n) is essentially free (O(log n)-ish) and catches n = p^k immediately — no factoring needed at all once you have p and k, just compute φ(n) = p^(k-1)(p-1) directly. See Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root. Do this before anything else; it costs nothing and a surprising number of "unfactorable" moduli in CTFs are secretly a power. 2. Lookup before compute. Query [factordb.com](https://factordb.com/) (or the factordb-pycli/factordb Python wrapper) with n before running any local algorithm. It has a large precomputed table and instantly resolves reused, previously-factored, or otherwise "known" moduli — a network round trip is cheaper than any CPU-bound method below. 3. Trial division for small factors. Cheap and complete for factors up to roughly 5-6 digits; sympy.factorint runs this automatically as its first pass. Don't hand-roll this — let the library's limit parameter bound it. 4. Close primes → Fermat. If the prompt/generator hints at nearby primes, run Fermat's method: search a upward from ceil(sqrt(n)), test a^2 - n for a perfect square each step (p = a-b, q = a+b). Cost scales with the gap |p-q|, so it's fast *only* for close primes — see Fermat Factorization — recovering p, q when the RSA primes were chosen too close for the loop and the "multiply by small k" trick when the gap is a bit too wide for a plain search. 5. General small-to-medium factor → Pollard's rho. This is the productive default once trial division and Fermat both fail and there's no explicit "close primes" hint: Floyd-cycle iteration on x -> x^2+c mod n, roughly O(n^(1/4)), effective when *some* factor is small (rough working range: up to ~10-12 digits) regardless of that factor's internal structure — past that range the O(n^(1/4)) cost catches up and ECM (step 7) takes over. sympy.factorint already wraps rho — see Pollard's Rho Factorization — finding a small-to-medium factor when trial division and Fermat fail. Try a different constant c on failure (return value == n means retry, not "no factor exists"). 6. Structurally weak prime → Pollard's p-1. Cheap probe to run alongside/after rho whenever a factor might have been chosen carelessly: gcd(a^M - 1, n) for M = lcm(1..B) reveals p if p-1 is B-smooth. Raise B if gcd returns 1, lower it or change the base a if it returns n. See Pollard's p-1 Factorization — when a prime's predecessor is smooth and Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't) for why smoothness is the actual mechanism (this generalizes: Pohlig-Hellman and index calculus exploit the same idea on the discrete-log side). 7. Stronger medium-factor extraction → ECM. When rho and p-1 both stall but you still suspect an unbalanced factor size, ecm.factor(n) in SageMath (GMP-ECM under the hood) reaches further than plain rho for medium-size factors without needing p-1's smoothness assumption. 8. Mixed/composite structure. For forms like n = p^2 * q that fail the pure perfect-power check, strip the residual cofactor with Pollard rho, then sum the per-factor φ contributions before deriving d — see Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root. 9. Only if all of the above fail on a genuinely balanced, unremarkable modulus: general-purpose sieves (quadratic sieve, GNFS via msieve/cado-nfs) are the textbook answer, but they only start to beat the methods above around ~400-bit composites and need serious tooling/compute — not something you improvise mid-CTF. Reaching this rung is itself a signal: stop and reconsider whether factoring n from scratch is really the intended path (see the last bullet under "the signal").

Once any factor is recovered, hand off to RSA Fundamentals — the routing hub: which artifact points to which attack to derive φ(n)/d and decrypt.

What does NOT work

- Running Fermat's method on primes that were never close. Cost grows with |p-q|; on genuinely random same-size primes it will not terminate in any practical time. Committing to a long Fermat run without a concrete "close primes" signal is the most common wasted-hours mistake in this branch — check the generator/prompt for the hint before starting, not after it's been running for 20 minutes. - Trusting Pollard's rho to break a balanced modulus. Rho's speed depends on the size of the *smallest* factor, not on n overall — two same-size, randomly-generated large primes give rho nothing to grab onto and it will churn indefinitely. If rho hasn't found anything after a reasonable timeout, that itself is a signal there's no small/medium factor to find, not a reason to let it run longer. - Skipping the perfect-power check because "the modulus doesn't look prime-power-ish." It's the cheapest test in the whole tree and mixed forms (n = p^2*q) don't announce themselves — always run it, even when nothing in the challenge suggests it. - Exhaustive trial division past a few million. It's complete but scales linearly with the smallest factor's size; past small-factor range it is strictly worse than rho for the same job and just burns wall-clock time for no benefit. - Treating "general factoring failed" as "the challenge is unsolvable." In practice it usually means factoring was never the intended attack — the real weakness is elsewhere (tiny/huge e, shared modulus, an oracle, a partial leak). A modulus that resists every branch above on a well-formed CTF challenge is a routing signal back to RSA Fundamentals — the routing hub: which artifact points to which attack, not a dead end. - Assuming Pollard's p-1 will eventually succeed by raising `B` indefinitely. It only works at all if p-1 is actually smooth; if it isn't, no bound B short of infeasible makes it terminate. Treat a failed p-1 attempt at a reasonable B (say 10^6-10^7) as evidence to move on, not as "try a bigger bound."

Related

RSA Fundamentals — the routing hub: which artifact points to which attack Fermat Factorization — recovering p, q when the RSA primes were chosen too close 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 Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't) Primality Testing — confirming a number is prime without factoring it Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction