# Complexity of Integer Factorization

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.

Posted on Categories proxies