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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Coron, JS., May, A. Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring. J Cryptology 20, 39–50 (2007). https://doi.org/10.1007/s00145-006-0433-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-006-0433-6