Q:

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.

A:

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.

