Welcome to the resource topic for 2004/208
Title:
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Authors: Jean-Sebastien Coron, 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.
ePrint: https://eprint.iacr.org/2004/208
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .