he problem is, thus, reduced to the factoring of a. It can be assumed that given N, all of the above tests, forming a "preamble" prove negative, and this is where Shor's algorithm must be implemented, as described in the following. Shor's factorization algorithm quantum Randomly chose XE [2,N-2] Calculate GCD(x, N), and if > 1, redo Find r, the order of x modulo N > Make measurement of quantum phase 5=s > Get r through the continued fraction expansion of 10 > Check that x" =1 mod N, and if not redo > Check that r is even and xr 12 # -1 mod N, if not go to 1 Calculate N'= GCD (y+1,N), N"=GCD(y-1,N) Factorize N',N" (as applicable) Figure 20.4 Step-by-step implementation of Shor's algorithm for nontrivial composite number N of bit size L, returning all factors of N'. Shor's algorithm Here is a step-by-step description, which is also schematically illustrated in Fig. 20.4. Step 1 Choose at random x E [2, N - 2] and test if x, N are co-prime. If the test fails, then another x must be selected. Step 2 Find r, , the order of X modulo N. This is done through the quantum phase measurement or estimation, = s'/r', and the continued fraction expansion algorithm, which yields r' =r, as described in Section 20.3. We then check that x = 1 mod N. As we have seen, there exists a small yet finite probability that this operation may fail, in which case this test is negative, and we may just try another phase measurement to obtain a different phase estimate, . Then we must ensure that r is even, and also that y=xr/12 = # - 1 mod N is a nontrivial solution. 13 If the test is negative, the whole process may be restarted at Step 1 (Theorem 2 ensures, however, that the success probability is high). Step 3 Calculate GCD(y + 1, N), which yields two factors of N, call them N', N". Then N', N" can be submitted to the aforementioned "preamble" tests, to identify whether further factorizing through Shor's algorithm may be warranted. Step 4 As applicable, N', N" may be factorized in turn, starting again from step 1. According to the above rend