Skip to main content
2 of 2
got links to work
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

Evidence for integer factorization is in $P$

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

user16007
  • 800
  • 1
  • 7
  • 15