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
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]