International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring

Authors:
Jean-Sébastien Coron
Alexander May
Download:
URL: http://eprint.iacr.org/2004/208
Search ePrint
Search Google
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 provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.
BibTeX
@misc{eprint-2004-12180,
  title={Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA, factoring.},
  url={http://eprint.iacr.org/2004/208},
  note={Extended version of a Crypto 2004 paper published by A. May. coron@clipper.ens.fr 12653 received 23 Aug 2004, last revised 23 Aug 2004},
  author={Jean-Sébastien Coron and Alexander May},
  year=2004
}