4 096 16 777 216 16 384 67 108 864 65 536 268 435 456 262 144 073 741 824 1 048 576 4 294 967 296 Order finding In this section, I shall describe the order-finding algorithm, which is based on the concept of number order in modular algebra. It will then be shown that there exists a unitary operator U that allows one to determine this order through the previously described phase-estimation circuit. Let us introduce the "order" concept first. In the foregoing, we shall call M = 2K the number of Fourier components, and from now on use N as the integer number that Shor's algorithm will attempt later to factorize into prime numbers. Assume, then, two positive integer numbers X, N, such that x < N, with the two numbers having no common divisor other than unity. It is said that their greatest common divisor (GCD) is unity, or equivalently, that the two numbers are co-prime. By definition, the order of X modulo N is the smallest nonzero integer r satisfying xr 1 mod N. (20.11) The order of x can also be conceived as the period of the powers x1, x2 modulo M. To give an example, let x = 4 and N = 13. The successive powers of 4 modulo 13 are listed in Table 20.1. It is seen that the period of the power series is r = 6, which also corresponds to the smallest nonzero integer for which 4 = 1 mod 13, according to the order definition in Eq. (20.11). Next, I shall describe how the quantum phase-estimation circuit makes it possible to determine the order of x modulo N, with a high probability of success and accuracy. For this, we first need to introduce the appropriate unitary operator U and its corresponding eigenstates and eigenvalues. We assume that given two integers X, N, satisfying x < and X being co-prime to M, there exists some operator Ux,N, which acts on the qubit ly) = |0), |1) as: (20.12) In the following, I shall just noteUx,N=Uforsimplicity. Second, let {|us)}s=0,1...r-1 be the set of r eigenstates of U, with associated eigenvalues exp(2irs/r), namely, satisfying U|us)=e (20.13) Shor's factorization algorithm /1/16)