# RSA: Fast factorization of N if d and e are known

I stumbled across this paragraph in a paper:

Hence, user b cannot decrypt C directly. But using e and d , user b can quickly factor N.

How is it possible to speedup the prime factorization when knowing e (public key) and d (private key)?

For clarification:

RSA provides us with these equations:

$n = pq$

$\phi = (p-1)(q-1)$

$gcd(e, \phi) = 1$

$de = 1\pmod{\phi}$

In order to determine $p$ and $q$ an attacker has to factor n which is not feasible. However the paper stated that it is easy to reconstruct $p$ and $q$ when a person knows both (his) private and public keys.

• It might help if you told us what $d$ and $e$ are. – Robin Chapman Nov 29 '10 at 11:03
• d is the private key and e is the public key – Chris Nov 29 '10 at 11:13
• Chris means: N = pq, with p and q odd primes; and ed = 1 mod (p-1)(q-1). – TonyK Nov 29 '10 at 12:17
• For "small" public exponents $e$ (i.e., $<\sqrt{n}$) you can rewrite your last equation as $de = 1 + k\varphi$ and divide this equation by $n$. As $\phi \approx n$ and as $k$ is an integer, you get $k$ by rounding $de/n$ and hence $\varphi$. For the general case see 8.2.2(i) in cacr.math.uwaterloo.ca/hac/about/chap8.pdf – j.p. Nov 29 '10 at 12:49

It is not difficult to prove that one can factor $\rm N$ in polynomial time given any multiple of $\rm \phi(N)$ (here $\rm \:de-1\:$).$\$ See, for example, Gary Miller: Riemann's hypothesis and tests for primality. 1976

NOTE $\$ This fact was well-known to the discoverers of RSA. Indeed they mention it explicitly in section IX of the original 1978 paper on RSA, which is quite readable.

Here is a probabilistic method that borrows ideas from an extension of the Rabin-Miller primality test which can be used for factoring pseudoprimes $n$ that are not strong pseudoprimes. The extension is described in Miller 1976, which is one of the references given in Bill Dubuque's answer.

It works when given some multiple $m$ of $\lambda(n)$ where $\lambda$ is Carmichael's lambda function. We assume that $n$ can be represented as $n=pq$ with unknown odd coprime $p,q>1$. The goal is to find a nontrivial factor of $n$.

1. Set $h$ to the largest odd divisor of $m$ by dividing out $2$ as many times as possible.
2. Choose a random $a\in\{2,3,\ldots,n-2\}$.
3. Compute $g=\gcd(a,n)$. This is probably $1$ for most $a$, but if not, you have found a nontrivial factor $g$ of $n$, so you are done. More importantly, the following steps implicitly assume that $\gcd(a,n)=1$.
4. Compute $b = a^h\bmod{n}$. We know that the multiplicative order of $b\pmod{n}$ is $1$ or some power of $2$. That order is also the least common multiple of the orders$\bmod{p}$ and$\bmod{q}$. We hope that those orders differ, which is likely (see below). In the following, we try to find the smallest order.
5. Compute $g=\gcd(b-1,n)$. Remark: If $b\equiv1\pmod{p}$, then $g$ will be divisible by $p$. And if $b\not\equiv1\pmod{q}$ yet, then $g$ will not be divisible by $q$, so $g$ will be a nontrivial divisor.
6. If $g=1$, replace $b$ with $b^2\bmod{n}$ and go to step 5. This will not loop forever because $b$ is known to reach $1\pmod{n}$ with a finite number of repetitions of step 6. That brings us to$\ldots$
7. If $g=n$, the multiplicative orders of $a^h\pmod{p}$ and $a^h\pmod{q}$ are equal. Then go to step 2, we need another $a$.
8. If you end up here, $g$ is a nontrivial factor of $n$.

How likely is it that the orders of $a^h$ are different$\bmod{p}$ and$\bmod{q}$?

Let $n=p_1^{e_1}\cdots p_k^{e_k}$ with pairwise distinct odd primes $p_i$ and positive integer exponents $e_i$. Write $\phi(p_i^{e_i}) = 2^{t_i} u_i$ with odd $u_i$ and set $t_{\text{min}} = \min\{t_1,\ldots,t_k\} \geq 1$. Note that $t_i$ does not depend on $e_i$. Note also that each $u_i$ divides the given $h$.

The $a$ that do not yield nontrivial factors of $n$ are those with order $\text{(odd number)}\cdot2^j$ in the unit group$\bmod{p_i^{e_i}}$, with the same $j$ for every $i$. Therefore such $j$ cannot exceed $t_{\text{min}}$.

For each such $j$, there are exactly $\phi(2^j)\,u_i = 2^{\max\{0,j-1\}} u_i$ non-yielding $a$ in the unit group$\bmod{p_i^{e^i}}$, namely, the primitive $2^j$-th roots of the $u_i$ solutions to $X^{u_i}\equiv 1\pmod{p_i^{e_i}}$. In the unit group$\bmod{p_i^{e_i}}$, those $a$ have a density of $2^{\max\{0,j-1\} - t_i}$. By chinese remaindering, we find that the non-yielding $a$ in the unit group$\bmod{n}$ have density \begin{align} \rho &= \sum_{j=0}^{t_{\text{min}}} \prod_{i=1}^k 2^{\max\{0,j-1\} - t_i} \\ &= \sum_{j=0}^{t_{\text{min}}} 2^{k\max\{0,j-1\} - (t_1 + \cdots + t_k)} \\ &= 2^{-(t_1 + \cdots + t_k)} \left(1 + \frac{2^{k\,t_{\text{min}}} - 1}{2^k - 1}\right) \\ &\leq 2^{-k\,t_{\text{min}}}\cdot 2^{k\,(t_{\text{min}}-1)+1} \\ &= 2^{-(k-1)} \end{align} Thus for composite $n$, the success probability is at least $50\%$ for each $a$ that makes it to step 4.