Recursive RSA-Style Factorization via Known φ(N) (Multi-Prime Moduli)

Updated 13 Sep 2026

• •

  What it is

  • •

    A generalization of the "factor N from a known (N,e,d) triple" trick to moduli built from more than two prime factors. If you know $N$ and its exact Euler totient $\phi(N)$ (not just an $(e,d)$ key pair), you can pick any exponent $e$ coprime to $\phi(N)$, compute a matching $d \equiv e^{-1} \pmod{\phi(N)}$, and run the same probabilistic "non-trivial square root of unity" factoring algorithm — it will split $N$ into two non-trivial factors, but if $N$ has more than two prime factors, at least one piece will still be composite. Recursing — checking primality of each resulting factor and re-splitting any that aren't prime yet, reusing the same $(e,d)$ pair — fully factors $N$ into all of its prime components, regardless of how many there are.

• •

  When to apply

  • •

    A challenge directly hands you both $N$ and $\phi(N)$ (rather than making you factor $N$ from scratch), and $N$ is explicitly stated (or suspected) to be a product of more than two primes.

• •

  Math

  • •

    Same core mechanism as RSA Factorization from Known (N, e, d) — for any $e$ coprime to $\phi(N)$ and $d\equiv e^{-1}\pmod{\phi(N)}$, $ed-1$ is a multiple of $\phi(N)$, letting the randomized square-root-of-unity search split $N$; since $\phi$ of any product of a subset of $N$'s prime factors still divides $\phi(N)$ (each $(p_i - 1)$ divides $\phi(N)$), the exact same $(e,d)$ pair remains valid for splitting any composite sub-factor recursively.

• •

  Worked example

  • •

    A toy modulus built from 5 distinct 48-bit primes, given only $(N, \phi(N))$: picking $e=65537$ and deriving $d$, then recursively applying the standard factor-from-$(n,e,d)$ split (checking primality at each step and re-splitting composite results with the same $e,d$) recovered all 5 original prime factors exactly.

• •

  Python

  • •

    def recursive_factor(n, e, d):
            factors = []
            stack = [n]
            while stack:
                cur = stack.pop()
                if is_prime(cur):
                    factors.append(cur)
                    continue
                p, q = factor_from_d(cur, e, d)   # same routine as the 2-factor case
                stack.extend([p, q])
            return factors
    

• •

  SageMath

  • •

    PyCryptodome's RSA.construct([n, e, d], consistency_check=False) conveniently exposes this splitting step directly as .p/.q attributes (it computes them internally using this exact algorithm) — a nice shortcut if working in Python with that library already available, rather than hand-rolling the search.

• •

  Related

  • •

    RSA Factorization from Known (N, e, d)

• •

  Cards

  • •

    Why does the same (e,d) pair remain valid for splitting a composite sub-factor of N, not just N itself?

    • •

      φ of any product of a subset of N's prime factors still divides φ(N) (each (p_i - 1) divides φ(N)), so ed-1 remains a multiple of that sub-factor's totient too.

  • •

    What extra step does this technique need beyond the basic two-factor version?

    • •

      Recursion: check whether each split-off piece is actually prime, and if not, re-run the same splitting routine on it.

◌ Explore connections in Graph view