CryptoDB
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Authors: | |
---|---|
Download: | |
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 |
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 }