Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter Sarnak's lectures where he mentions that he does not believe factoring is not in $P$.

What evidence is there that integer factorization is in $P$ other than the fact that polynomial factorization is in $P$?


1 Answer 1


I don't think there is any compelling evidence that integer factorization can be done in polynomial time. It's true that polynomial factoring can be, but lots of things are much easier for polynomials than for integers, and I see no reason to believe these rings must always have the same computational complexity. (Strangely, if you do believe that, it means the shortest lattice vector problem should also be efficiently solvable, but it doesn't seem to tell you anything about discrete logarithms. This puzzles me, since the parallels between factoring and discrete logs are also strong.) It's also true that primality testing can be done in polynomial time, but that is a fundamentally different problem: when a modulus is prime, it has enormous consequences for modular arithmetic, and it is not difficult to test for primality by looking for those consequences, but the actual methods shed no light on factoring.

On the other hand, there is also no compelling evidence that factoring can't be done in polynomial time (see http://research.microsoft.com/~cohn/Thoughts/factoring.html for a little more detail about this).

At our current level of knowledge, I view the complexity of factoring as a matter of opinion, speculation, and wishful thinking, not principled arguments. By contrast, there are exceedingly good reasons why the Riemann hypothesis should be true, and good reasons why P shouldn't equal NP. I'm certainly open to arguments that fall far short of rigorous proof; I've just never heard a convincing one about the complexity of factoring.

My interpretation of Sarnak's belief isn't that he sees some good reasons other people don't appreciate. Rather, it just feels plausible to him, and he's perhaps a little annoyed that lots of people firmly believe the opposite for no good reason, so he makes a point of stating a strong opinion.

  • $\begingroup$ What does it mean by "it means the shortest lattice vector problem should also be efficiently solvable"? $\endgroup$
    – Turbo
    Commented Jul 25, 2015 at 7:00
  • $\begingroup$ that probably means we can find the shortest vector in a lattice `efficiently'.. which is provably np-hard in some cases, but not known to be easy or hard in general.. we just don't know $\endgroup$ Commented May 15 at 16:42

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.