Skip to main content
1 of 2
user16007
  • 800
  • 1
  • 7
  • 15

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$. www.austms.org.au/tiki-download_file.php?fileId=161

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