Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

as I understand it would have little effect since it's implicitly assumed to be that way, might be wrong though


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.


The 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.


Factorization is not NP, it's "easier"


It's definitely in the class, but it's undecided which subclass it belongs to.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: