MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
The fact that primality is in $P$, and intuitively that feels like a rather big part of the problem? – Federico Poloni Oct 28 '11 at 9:15
up vote 32 down vote accepted

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 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.

share|cite|improve this answer
What does it mean by "it means the shortest lattice vector problem should also be efficiently solvable"? – Turbo Jul 25 '15 at 7:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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