 Shor’s algorithm exploits the ingenious number theoretic argument that two prime factors \(p,q\) of a positive integer \(N=pq\) can be found by determining the period of a function \(f(x) = y^x \textrm{mod} N,\) for any \(y &lt; N\) which has no common factors with \(N\) other than 1 (Nielsen and Chuang 2000 App. 4). The period \(r\) of \(f(x)\) depends on \(y\) and \(N\). Once one knows it, one can factor \(N\) if \(r\) is even and \(y^{\,\frac{r}{2}} \neq -1\) mod \(N\), which will be jointly the case with probability greater than \(\frac{1}{2}\) for any \(y\) chosen randomly (if not, one chooses another value of \(y\) and tries again). The factors of \(N\) are the greatest common divisors of \(y^{\,\frac{r}{2}} \pm 1\) and \(N\), which can be found in polynomial time using the well known Euclidean algorithm. In other words, Shor’s remarkable result rests on the discovery that the problem of factoring reduces to the problem of finding the period of a certain periodic function \(f: Z_{n} \rightarrow Z_{N}\), where \(Z_{n}\) is the additive group of integers mod \(n\) (Note that \(f(x) = y^{x}\ \textrm{mod}\ N\) so that \(f(x+r) = f(x)\) if \(x+r \le n\). The function is periodic if \(r\) divides \(n\) exactly, otherwise it is almost periodic). That this problem can be solved efficiently by a quantum computer is hinted at by Simon’s algorithm, which considers the more restricted case of functions periodic under bit-wise modulo-2 addition as opposed to the periodic functions under ordinary addition considered here.