Cryptology ePrint Archive: Report 2004/208

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

Jean-Sebastien Coron and Alexander May

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.

Category / Keywords: public-key cryptography / RSA, factoring.

Publication Info: Extended version of a Crypto 2004 paper published by A. May.

Date: received 23 Aug 2004, last revised 23 Aug 2004

Contact author: coron at clipper ens fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040823:153005 (All versions of this report)

Short URL: ia.cr/2004/208