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

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

## 1 Answer

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.

-