Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring

摘要: We address one of the most fundamental problems concerning RSA cryptoscheme: Does knowledge public key/ secret key pair (e,d) yield factorization N=pq in polynomial time? It is well-known that there a probabilistic time algorithm on input (N,e,d) outputs factors p and q. present first deterministic N provided e,d < φ(N) p, q are same bit-size. Our approach an application Coppersmith’s technique for finding small roots bivariate integer polynomials.