# Assuming that NP = RP, how would this impact cryptography?

In terms of complexity classes, we assume that NP = RP. In other words, we assume that there is a randomized algorithm that solves a NP complete problem (and through polynomial time reductions, all of them in the class ) in polynomial time (assume quadratic ) with high probability. Also assume that the algorithm can be efficiently coded and implemented. How would this impact cryptography, in particular RSA?

• This question is not related to my older question "Is it possible to attack RSA with a WalkSat derivative? ". Behind the algorithm described there, a long time ago I found a flaw in the mathematics. – Cristian Dumitrescu Sep 4 '17 at 1:17
• For the purposes of cryptography, there is likely (I would like to say almost certainly) no distinction between P=NP and RP=NP in terms of practical implications. So, these answers should apply. – otus Sep 4 '17 at 4:59