TY - JOUR
AU - Subhamoy Maitra
AU - Santanu Sarkar
PY - 2012/03/13
Y2 - 2020/04/07
TI - On Deterministic Polynomial-time Equivalence of Computing the CRT-RSA Secret Keys and Factoring
JF - Defence Science Journal
JA - DSJ
VL - 62
IS - 2
SE - Computers & Systems Studies
DO - 10.14429/dsj.62.1716
UR - https://publications.drdo.gov.in/ojs/index.php/dsj/article/view/1716
AB - Let N = pq be the product of two large primes. Consider Chinese remainder theorem-Rivest, Shamir, Adleman (CRT-RSA) with the public encryption exponent e and private decryption exponents dp, dq. It is well known that given any one of dp or dq (or both) one can factorise N in probabilistic poly(log N) time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice-based deterministic poly(log N) time algorithm that uses both dp, dq (in addition to the public information e, N) to factorise N for certain ranges of dp, dq. We like to stress that proving the equivalence for all the values of dp, dq may be a nontrivial task.Defence Science Journal, 2012, 62(2), pp.122-126, DOI:http://dx.doi.org/10.14429/dsj.62.1716
ER -