Perfect-Power Modulus (n = p^k) — trivial factoring via integer k-th root

When the RSA modulus is not a product of two distinct primes but a single prime raised to a power, n = p^k, factoring is not hard at all: take the integer k-th root of n to recover p directly, then compute φ(n) = p^{k-1}(p-1) and derive d — no general-purpose factoring algorithm is ever needed.

The signal that gives it away

- General-purpose factoring "fails oddly": factordb comes back empty or times out, sympy.factorint(n) hangs, even though n isn't unusually large — that mismatch (full-size modulus, otherwise-competent factoring tools stall) is itself a tell that n doesn't have the usual two-large-distinct-primes shape. - gcd-based probes against n come back with n itself rather than a proper factor — a classic symptom of n being a prime power rather than a semiprime. - Source or generator code visibly does p**k (or similar) instead of p*q when building the modulus. - n is an exact integer power — this is checkable directly and cheaply, so treat it as a mandatory first probe on *any* unfamiliar RSA modulus, not just ones that already look suspicious: run the perfect-power test before reaching for factordb or Pollard's rho, since it's the fastest possible check and rules out (or confirms) the easiest case first.

How to exploit it

1. Detect the power and base in one call: ``python from sympy import perfect_power, isprime, mod_inverse res = perfect_power(n) # returns (p, k) or False if res: p, k = res assert isprime(p) and p**k == n phi = p**(k-1) * (p-1) # φ(p^k) = p^(k-1) * (p-1) d = mod_inverse(e, phi) m = pow(c, d, n) ` 2. If you already suspect k=2 specifically (a squared prime), the lighter check p, exact = integer_nthroot(n, 2) suffices without pulling in the general perfect_power search. 3. For **mixed forms** like n = p^2 * q (a prime power times a separate distinct prime, not a pure prime power), perfect_power will correctly return False` — this is not the same case. Factor the residual cofactor with Pollard's Rho Factorization — finding a small-to-medium factor when trial division and Fermat fail once you've pulled out the repeated factor, then sum the per-factor φ contributions (φ(p^2)*φ(q) style, multiplicativity of φ over coprime factors) before computing d through the standard RSA Fundamentals — the routing hub: which artifact points to which attack machinery. 4. Once p and k are known, everything downstream — computing d, decrypting c, or forging a signature — is identical to the standard RSA Fundamentals — the routing hub: which artifact points to which attack recipe; the only nonstandard step is the totient formula for a prime power instead of (p-1)*(q-1).

What does NOT work

- **Confusing this with Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n.** If instead the *ciphertext* (not the modulus) looks like it could be a perfect power — i.e. c = m^e with no modular wraparound because m^e < n — that is a completely different situation: an integer e-th root of the ciphertext directly recovers the message, and n's factorization is irrelevant. Don't waste time running perfect_power on n when the actual signal is a small e and a small m; check which object (the modulus or the ciphertext) is the one that's the perfect power before picking a technique. - Running Fermat factorization here. Fermat Factorization — recovering p, q when the RSA primes were chosen too close targets n = p*q where p and q are two *distinct* primes close to each other near sqrt(n) — a completely different structural weakness. Fermat's difference-of-squares search does always terminate and, when it stops, does return a mathematically valid split of n (a proper factorization, or — if no closer pair of factors exists — the trivial 1 × n, confirming primality-like structure rather than misfiring); it can't return an incorrect split, since any a, b it reports satisfy (a-b)(a+b) = n by construction. The real problem for a pure prime power is efficiency, not correctness: with only one prime factor, the only factor pairs of n are (p^i, p^{k-i}), and unless k is even (in which case n is a perfect square and Fermat finds p^{k/2} in its very first step) there's no pair of close, distinct proper factors near sqrt(n) — so the search can take an impractically large number of iterations before it terminates. Detect the perfect-power case first — it's cheaper to check and, if positive, makes Fermat entirely unnecessary (and avoids the slow case). - Throwing general factoring tools at it blind before checking for the power structure. factordb lookups and sympy.factorint are not optimized for this case and can stall or waste your CTF time budget on a modulus that a one-line perfect_power(n) call solves instantly. The perfect-power check is close to free — always run it before escalating to anything from Integer Factorization Methodology — which factoring attack to try, in what order's heavier branches. - **Assuming a mixed modulus like p^2 * q is "the same attack."** It looks superficially similar (a repeated prime factor is present) but perfect_power(n) returns False for it, and applying the pure prime-power totient formula to the whole n gives the wrong φ and a d that doesn't decrypt anything. Mixed forms need the cofactor pulled out and factored separately (see step 3 above) before the totient can be assembled correctly.

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 Fermat Factorization — recovering p, q when the RSA primes were chosen too close Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n