I am reading the Handbook of Applied Cryptography and on page 99 the authors write , after showing that $QRP \le_P FACTORING$:

It is believed that the $QRP$ is as difficult as the problem of factoring integers, although no proof of this is known.

I am not quite sure what "as difficult" means, do they say that it is assumed that $QRP \ge_P FACTORING$?


1 Answer 1


I would put it as "it is conjectured" rather than "it is assumed", but otherwise, yeah...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.