Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring.
Jean-Sébastien Coron, Alexander May · 2004
Abstract. 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 <ϕ(N). Our approach is an application of Coppersmith’s technique for finding small roots of univariate modular polynomials. Key words. RSA, Coppersmith’s theorem. 1.