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

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$ ?

• First of all, welcome to Crypto Stack exchange. You may want to take a look at di-mgt.com.au/rsa_factorize_n.html. – chelsea Sep 19 '18 at 6:14
• It is not possible that there isn't at least one duplicate of this question on this site. Have you done a search? – Thomas Sep 19 '18 at 8:23
• @Thomas: the closest I found is this question, but it asks whether $N$ can be factored, not how. The accepted answer focuses on that without explicitly giving the algorithms it refers to. Other answers are not algorithm-centric either, and give explanations assuming $e\,d\equiv1\pmod{\phi(N)}$ for one and $d=e^{-1}\bmod\phi(N)$ for another, which does not hold for all valid $(N,e,d)$. – fgrieu Sep 19 '18 at 9:51
• Sorry everyone. It's my mistake. Thank you for all – user61922 Sep 19 '18 at 12:28

## Algorithm

An RSA modulus $$N$$ product of large distinct primes can be factored given $$(N,e,d)$$ per:

1. Compute $$f\gets e\,d-1$$, and 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, 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.

• that's great. Is there a reference, or some context about where this algorithm appeared? – Cédric Van Rompay Sep 19 '18 at 10:12