Algorithm to factorize $N$ given $N$, $e$, $d$

Question

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key.

How can I compute $p$ and $q$, the primes factor of $N$ ?

Answer 1

Algorithm

An RSA modulus $N$ product of large distinct primes can be factored given any non-zero multiple $f$ of $\lambda(N)$ (where $\lambda$ is the Carmichael function), including $f=\varphi(N)$ (the Euler totient), or with $(N,e,d)$ yielding such $f$ as $f\gets e\,d-1$, as follows:

1. Express $f$ as $2^s\,t$ with $t$ odd
2. Set $i\gets s$ and $a\gets2$
3. Compute $b\gets a^t\bmod N$ , and if $b=1$ then
   • set $a$ to the next prime, and proceed at 3
4. If $i\ne1$ then
   • compute $c\gets b^2\bmod N$ , and if $c\ne1$ then
     • set $b\gets c$, decrease $i$, and proceed at 4
5. If $b=N-1$ then
   • set $a$ to the next prime, and proceed at 3
6. Compute and output $p\gets\gcd(b-1,N)$ , and $q\gets N/p$.

For standard RSA where $N$ has 2 distinct factors, we have fully factored $N$. Otherwise, $p$ or/and $q$ won't be prime, just re-run the algorithm from step 2 replacing $N$ by any still unfactored component, until all the prime factors of $N$ have been pulled out.

---

Justification

In an RSA context, $N$ has no small prime factor, thus the algorithm's $a$ at step 3 will remain small enough that $\gcd(a,N)=1$ will hold (if it did not, $a$ would be a factor of $N$ found by trial division; a trivial modification of the algorithm additionally handles $N$ with such small factors).

For any valid RSA triple $(N,e,d)$, it holds that $\left(a^e\right)^d\bmod N=a$ for any integer $a$ in $[0,n)$ (because textbook RSA decryption works).

Thus for any $a$ used in the algorithm, $a^{e\,d-1}\bmod N=1$ holds, that is $a^f\bmod N=1$ for the $f$ of step 1.

The $t$ and $s$ of step 1 are uniquely defined, with $s>0$, and $\left(a^t\right)^{\left(2^s\right)}\bmod N=1$.

For most $N$, step 3 will quickly find an $a$ with $a^t\bmod N\ne1$. Argument: Since $N$ is squarefree, by the Chineese Remainder Theorem, an $a$ coprime with $N$ is rejected at step 3 iff $a^t\bmod p=1$ for all primes $p$ dividing $N$. Since $t$ is odd, if $a^t\bmod p=1$ holds for $a$, then $\tilde a^t\bmod p=p-1\ne1$ for $\tilde a=-a\bmod p$. Thus for $a$ coprime with $N$ chosen randomly in some large interval, the probability of $a^t\bmod p=1$ is $\le\frac12$. That is independently for each $p$, thus $a^t\bmod N\ne1$ has probability $\ge1-2^{-m}$ where $m\ge2$ is the number of factors of $N$. Using the consecutive primes $a$ (rather than random $a$) works well in practice for random instances of the problem (I have no proof, and one may require the Extended Riemann Hypothesis).

Before each iteration of step 4, it holds $1<b<N$, with $i\ge1$, and $b^{\left(2^i\right)}\bmod N=1$ ; thus after at most $s-1$ computations in step 4 we reach step 5 with $b\bmod N\ne1$ and $b^2\bmod N=1$.

Step 5 excludes the case $b=N-1$, which is rare in practice (I'm looking for an argument).

Thus at step 6, $\gcd(b-1,N)$ is a non-trivial factor of $N$.

---

References

A similar algorithm was hinted at in the original RSA paper: Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM 1978; see last two paragraphs of section IX-C. That uses and references the proof of a primality test in Gary L. Miller's Riemann's Hypothesis and tests for primality, in proceedings of STOC 1975.

A more detailed exposition is in Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, CRC Press 1997; see last paragraph of section 8.2.2 (i).

That answer's algorithm differs by using incremental primes $a$ rather than random $a$. That makes the algorithm deterministic (not its runtime), and works well in practice. As a minor aside, the number of modular squares computed in step 4 is minimized by using a test of $i$ rather than an additional last square.

Note: Simpler variations restrict to $b=a^t\bmod N$ or $b=a^{f/2}\bmod N$, but require testing sizably more $a$ when $s$ is large, which occasionally happens. Some justifications assume $d=e^{-1}\bmod\varphi(N)$ or $e\,d\equiv1\pmod{\varphi(N)}$, which does not consistently hold in modern RSA: for FIPS 186-4 that has probability less than $\frac1 3$, because $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ is required.

For a (different) deterministic polynomial-time algorithm, see Jean-Sebastien Coron and Alexander May's Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, in JoC 2007.