4 ms·
RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wr
by chupasaurus 8y ago
RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wrong) it could be used to get private keys from public ones in a matter of days.
- nabla9 8y agoThe proof itself would not give factorization algorithm. Even if P = NP, prime factorization can be very time consuming to solve. The prime factorization problem is in the NP class, but we don't know if it is NP-hard.
- raverbashing 8y agoFactorization is not NP, it's "easier"
- chupasaurus 8y agoIt's definitely in the class, but it's undecided which subclass it belongs to.