Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$. Is there evidence that no extension of Coppersmith technique will accomplish factoring $N=PQ$ in polynomial time?

Technically I am asking possibility of no possible way to reduce factoring to finding integer roots of polynomials. Is there contradiction in literature that supports possibility that if you can solve polynomial equations within bounds on the unknowns that are large enough to allow factorization, then you should also be able to solve polynomial equations with exponentially many solutions, which cannot be done in polynomial time?

This seems to imply no such evidence exists Reduction from factoring to solving Pell equation. However I do not know surely.

Is there any other such reduction known? Is there literature references?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.