Complexity of Integer Factorization

Question

In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142):

A language $L$ is in NP if there is a turing machine $M$ with the following properties.

1. If $x\in L$ then there exists a witness string $w$ such that $M$ halts in the state $q_Y$ ("yes state") after a time polynomial in $|x|$ when the machine is started in the state $x$-blank-$w$.
2. If $x \not \in L$ then for all strings $w$ which attempt to play the role of a witness, the machine halts in state $q_N$ ("no state") after a time polynomial in $|x|$ when $M$ is started in the state $x$-blank-$w$.

This definition is motivated by the factoring decision problem, where they identify "witness strings" $w$ with possible factors of $x$.

My confusion is, based on how NP is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $x$, start the factoring turing machine $M$ in the state $x$-blank-$w$ for all $w < x$, and check whether the machine ever halts in $q_Y$. Since there are $O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $x$ has factors in polynomial time.

Clearly this shouldn't work, but I am unsure where the flaw in my logic is.

Answer 1

The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in pseudo polynomial time.

Additionally, it seems that you are confusing factoring and primality testing. A possible decision version of factoring is given $(n,x)$ check whether $n$ has a factor $\le x$ (while your proposal refers to the case where only $n$ is given, and you loop to find a possible factor). While checking if a given number is prime is known to be in $P$, FACTORING is believed to lie outside of P.