 15 # 1 mod 15, which shows that the solution xr/2 = 82 = 64 is valid (it can also be checked that x = 84 = 1 mod 15, but this test does not need to be made). Therefore, two factors N', N" of N = 15 are N' = GCD(x"/2 - 1, N) = GCD(63, 15) = 3, N" = GCD(x"/2 + 1, N) = GCD(65, 15) = 5, which concludes Shor's factorization algorithm. Since both factors N', N" are prime, the factorization of N is also complete! As we have seen, however, the algorithm succeeded in this example because (a) one of the four possible measurements yielded a valid convergent of Q, (b) the order r turned out to be even, and (c) the condition xr/2 # - 1 mod 15 was satisfied. In the case where any of these prerequisites is not met, the algorithm would have failed. Provided we obtained a convergent of Q, it turned out that the random selection x = 8 was a "lucky" one. Then what are the other alternatives Shor's factorization algorithm Table 20.4 Possibilities of selecting X towards the factorization of N = 15 through Shor's algorithm, with corresponding order r, test xr/2 # 1 mod N, and number m of convergents. xr/2 mod N and chances of failure under any other random selection for x? The answer is provided in the following discussion. Discussion To factorize N = 15, we must randomly select x in the interval x E [2, N - 2], with the condition that (x, N) be co-prime. This leaves X = 2, 4, 7, 8, 11, 13 as the only six possibilities of fully implementing the algorithm. We then use a computer spread- sheet to obtain the order r "classically" (this being not part of Shor's algorithm, but just a computing means for the purpose of the analysis). The results are listed in Table 20.4, along with the test xr/2 mod N and the number m of convergents. It is seen from the table that the order of X is either r = 2 (x = 4, 11) or r = 4 (x = 2, 7, 8, 13), and that both pass the test xr/2 # +1 mod N. Consider the case r = 4, and assume the register size K = 2 11 = 2048 (L = 4 bits). This case is wholly identical to the previously described example where X = 8 wa