THE GARDEN

RSA Factorization from Known (N, e, d)

Updated 13 Sep 2026

• •

  What it is

  • •

    If an attacker learns a valid (public modulus $N$, public exponent $e$, private exponent $d$) triple for an RSA key — even without directly knowing $p$ or $q$ — the modulus can be factored efficiently, in randomized polynomial time. The key fact: $k = ed - 1$ is a multiple of $\phi(N)$, so for (almost) any base $g$, repeatedly halving the exponent of $g^k \bmod N$ (writing $k = 2^r t$ with $t$ odd, squaring up from $g^t$) will, with probability at least $1/2$ per random $g$, land on a non-trivial square root of unity modulo $N$ partway through — a value $x \ne \pm 1$ with $x^2 \equiv 1 \pmod N$ — at which point $\gcd(x-1, N)$ splits off a genuine factor, exactly the same mechanism as RSA Fixed-Point Leakage (Unconcealed Messages) → Factorization and Miller-Rabin's compositeness witnesses.

• •

  When to apply

  • •

    You've obtained a private exponent $d$ for a key without its factorization directly (e.g. it's your own real key, provided as $(N,e,d)$, and you want to recover $p,q$ from it programmatically).

• •

  Math

  • •

    $ed \equiv 1 \pmod \phi(N) \Rightarrow ed−1=k \phi(N)$ for some integer $k$. Write $ed-1 = 2^r t$, $t$ odd. For random $g$, compute $y = g^t \bmod N$; if $y \ne \pm 1$, repeatedly square it up to $r-1$ times, checking whether the result becomes 1 — if so, the previous value is (with good probability) a non-trivial square root of unity, and $\gcd(y-1, N)$ reveals a factor. Retry with a fresh random $g$ if an attempt doesn't produce one.

• •

  Worked example

  • •

    Toy 256-bit RSA key with $e=65537$: computing $d$ normally, then running only the factor-from-$(N,e,d)$ procedure (as if $p,q$ were unknown) correctly recovered the exact original $\{p, q\}$ pair.

• •

  Python

  • •

    def factor_from_d(N, e, d):
        k = e*d - 1
        t = k
        r = 0
        while t % 2 == 0:
            t //= 2
            r += 1
        while True:
            g = random.randrange(2, N - 2)
            y = pow(g, t, N)
            if y in (1, N - 1):
                continue
            for _ in range(r):
                x = pow(y, 2, N)
                if x == 1:
                    fac = math.gcd(y - 1, N)
                    if 1 < fac < N:
                        return fac, N // fac
                    break
                y = x
    

• •

  SageMath

  • •

    Not particularly relevant — this is a direct probabilistic algorithm, equally simple in either language.

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What single fact about ed-1 makes this factorization algorithm work?

    • •

      ed - 1 is a multiple of φ(N), which lets you replicate the "find a non-trivial square root of unity" trick used by Miller-Rabin, without knowing φ(N)'s value directly.

  • •

    Why might a single random base g fail to produce a factor, and what's the fix?

    • •

      With roughly 50% probability per random g, the squaring sequence hits -1 before ever revealing a non-trivial root; simply retrying with a fresh random g resolves it.

◌ Explore connections in Graph view