Deterministic polynomial-time equivalence of computing the RSA secret key and factoring

We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key pair (e, d) yield the factorization of N = pq in polynomial time? It is well known that there is a probabilistic polynomial-time algorithm that on input (N, e, d) outputs the factors p and q. We present the first deterministic polynomial-time algorithm that factors N given (e, d) provided that e, d < phi(N). Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.