Hot answers tagged quantum-cryptography
That tells us those problems are in BQP. This answer describes a way of reducing factoring to SAT. More elaborate approaches will give reductions from RSA or ECC to SAT. On the other hand, if there is a polynomial-time reduction from an NP-hard problem to RSA or ECC then BQP ∩ UP ∩ coUP = NP .
Only top voted, non community-wiki answers of a minimum length are eligible