For any positive integer \(N\), the fundamental theorem of arithmetic says that \(N\) can be expressed as a product of prime numbers alone. That is, there exist distinct prime numbers \(p_i\) and positive integers \(q_i\) such that
\[N=p_1^{q_1}p_2^{q_2}\dots p_m^{q_m}.\]
The factoring problem can thus be phrased as follows.
The Factoring Problem
Input: A positive integer \(N\).
Problem: Determine distinct prime numbers \(p_i\) and integers \(q_i\) such that \[N=p_1^{q_1}p_2^{q_2}\dots p_m^{q_m}.\]
The factoring problem becomes more or less difficult depending on the nature of the integer \(N\) to be factored. If \(N\) is even, then \(2\) will always be a factor of \(N\). Moreover, some power of \(2\) may be a factor of \(N\), and each such power of \(2\) will also be a factor of \(N\). Therefore, assume \(N\) is odd so that \(2\) is not a factor of \(N\). A slightly harder case is if \(N=p^q\) for some odd prime \(p\) and integer \(q\). However, even this scenario is easy to solve classically because it must always be the case that \(q\leq log_2(N)\). So by simply computing the first \(log_2(N)\) roots of \(N\), say \(N^{1/k}\) for some \(k\leq log_2(N)\), and then checking to see if \(N^{1/k}\) is a prime number determines a \(p\) such that \(p^k=N\). This test would need to be repeated at most \(log_2(N)\) times, and since the problem of determining whether some integer is prime is in \(\mathbf{P}\) the problem of finding a prime factor \(p\) such that \(p^q=N\) will have a time complexity corresponding to some polynomial in \(log_2(N)\).
The remaining case to consider in factoring \(N\) is when \(N\) is an odd, non-prime power--that is, \(N\) has at least two distinct odd prime factors. In this case the integer can be expressed as \(N=N_1N_2\) for two positive integers \(N_1\) and \(N_2\) both less than \(N\). Each \(N_i\) is a factor of \(N\), which can in turn be factored further if the \(N_i\) is not itself a prime integer. Hence, the problem of factoring \(N\) in this case can be reduced the problem of splitting an odd, non-prime power \(N\).
Splitting an Odd, Non-prime Power
Input: An odd positive integer \(N\) such that \(N\) is not a power of some prime.
Problem: Determine positive integer factors \(N_1\) and \(N_2\) less than N such that \(N=N_1N_2\).
For any factorization of \(N\) as \(N=N_1N_2\), it must be the case that both \(N_i\) are such that \(N_i\leq \sqrt{N}\). Therefore, the problem of completely factoring an integer \(N\) can be reduced to splitting some odd, non-prime integer \(N\) at most \(log_2(N)\) times. This reduction can be done classically and deterministically placing the complexity of such a reduction in the class \(\mathbf{P}\).
Finally, suppose we are in the scenario where \(N\) is an odd, non-prime power. Denote by \(gcd(x,y)\) the greatest common divisor of two integers \(x\) and \(y\), and call two numbers coprime if and only if \(gcd(x,y)=1\). Let \(N\) be some integer to be factored, and \(x\) be an integer such that \(0<x<N\). If \(N\) and \(x\) are not coprime, then \(gcd(x,N)>1\) will be a nontrivial factor of \(N\). Moreover, \(gcd(x,N)\) can be computed efficiently through classical means such as the extended Euclidean algorithm in time \(O(log_2(N))\).\cite{knuth}
Instead, suppose that some integer \(0<x<N\) is chosen such that \(x\) and \(N\) are coprime. Then since \(gcd(x, N)=1\), a non-trivial factor cannot be found by simply evaluating \(gcd(x,N)\). Then for \(x\) coprime to \(N\), consider the following sequence of numbers
\[1=x^0 (mod\hspace{2mm}N),\hspace{2mm} x^1 (mod\hspace{2mm}N),\hspace{2mm} x^2 (mod\hspace{2mm}N), ...\]
This sequence will necessarily begin to repeat itself after finitely many terms. That is, the function
\[f_{x,N} : \{0,1,2,...\} \rightarrow \{0,1,2,...\},\] sending \[a\mapsto x^a (mod\hspace{2mm}N),\]
has a period \(r\), which is the smallest positive integer \(r\) that satisfies \(f_{x,N}(a+r)=f_{x,N}(a)\) for all \(a\). Such an \(r\) also satisfies \(x^r=1 (mod\hspace{2mm}N)\), and will be called the order of \(x\).
Suppose that the period \(r\) of the function \(f_{x,N}(a)=x^a (mod\hspace{2mm}N)\) is given. In addition, suppose that \(r\) is an even number. The it follows that
\[x^r =1 (mod\hspace{2mm}N) \Longleftrightarrow (x^{ \frac{r}{2}})^2 = 1 (mod\hspace{2mm}N) \Longleftrightarrow (x^{ \frac{r}{2}})^2-1 = 0 (mod\hspace{2mm}N) \Longleftrightarrow\]
\[ (x^{\frac{r}{2}} +1)(x^{ \frac{r}{2}}-1)= 0 (mod\hspace{2mm}N) \Longleftrightarrow (x^{ \frac{r}{2}} +1)(x^{ \frac{r}{2}}-1) = kN\] for some \(k\).
Since \(x>1\), this implies both \(x^{ \frac{r}{2}} +1>1\) and \(x^{ \frac{r}{2}}-1>1\), so that \(k>0\). Therefore, \(x^{ \frac{r}{2}} +1\) and \(x^{ \frac{r}{2}}-1\) must share a factor with \(N\). Now suppose that \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) are not multiples of \(N\). Then the common factor shared with \(N\) must be less than \(N\). Calculating \(gcd(x^{ \frac{r}{2}} +1, N)\) and \(gcd(x^{ \frac{r}{2}}-1, N)\) would then yield two nontrivial factors of \(N\). It has been shown that if we know \(x\) and \(r\) meeting the criterion above, then we could effectively determine nontrivial factors of \(N\). Therefore, the problem of splitting an odd, non-prime integer \(N\) can be reduced to the problem of finding the order \(r\) of a random element \(x\) \(mod\hspace{2mm}N\).
The Order Finding Problem
Input: Integers \(x\) and \(N\) such that \(gcd(x,N)=1\)
Problem: Find the order \(r\) of \(x\) \(mod\hspace{2mm}N\), where \(x^r=1 (mod\hspace{2mm}N)\).
In this reduction it was required that \(r\) be an even number so that \(r/2\) is also an integer. Since \(x\) such that \(0<x<N\) is initially chosen at random, it is possible to choose a \(x\) where \(r\) is not even or that at least one of \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) is a multiple of \(N\). Such an \(x\) would not yield a factor using the method described above. In this case, to successfully factor \(N\) by reducing the problem to order finding, another \(x\) would have to be chosen that does meet the necessary criterion. However, it can be shown that with probability greater than \(1/2\), an \(x\) can be chosen such that \(r\) is even and \((x^{ \frac{r}{2}} +1)\) and \((x^{ \frac{r}{2}}-1)\) are not multiples of \(N\). This reduction of factoring to order finding has a probabilistic classical algorithm placing the problem corresponding to this reduction in the complexity class \(\mathbf{BPP}\).\cite{mosca}
The previous arguments only showed that an integer \(N\) can be factored if the order \(r\) of some integer \(x\) coprime to \(N\) is given, but did not offer any means of actually finding such an \(r\). If an algorithm exists for finding these orders, and if it can accomplish the task efficiently, then an efficient algorithm for the factoring problem would follow through the series of reductions since each reduction cold be done efficiently as well. Its important to note that all these previous reductions are classical, and either deterministic or probabilistic. That is, no quantum algorithm has been used thus far in attempting to solve the factoring problem. The next section will explicitly show how to find orders using an efficient quantum algorithm making use of the eigenvalue estimation algorithm, which will in turn solve the factoring problem efficiently.