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

## 1 Answer

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.