e implementation of Shor's algorithm is a trial and error process: some values of X do not work out, and in the best case, some register measurements fail to yield any convergent, as we have seen with the N = 15 factorization example. This discussion leads to another question: are some composites easier to factorize than others under Shor's algorithm, corresponding to higher values of the II indi- cator? In an attempt to address this question, we may analyze the periods of the first composite numbers and see which ones may present the least factoring diffi- culty or the highest II. Consider, then, the composites of the type N = pq (with p, q primes), which satisfy the two conditions: (a) N is not even, and (b) there are no integers a, b (a, b > 2), such that N = ab. With a list of the first primes limited to p, = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, excluding p, q = 2, the set of eligible composites comes to 55 numbers ranging from N = 15 to N = 1147, as illustrated in Table 20.5. The selection listed in the table, thus, justifies that N = 15 is the first composite candidate to implement Shor's algorithm. Considering the highest number of the selection, N = 1147, determining the period would require one to compute the successive powers of 1145P, which scale as 10px1n(1145)/in(10) 2 103p and, thus, rapidly leads to an overflow. If, on the other hand, we limit the scope to N < 100, i.e., max(N) = 91, the computation remains tractable (89P 2 101.9p), at least with a personal computer. A period-finding computer program can easily be implemented, 14 yielding tabulation of r for each value x E [2, N - 2], along with the validation tests {xr/2 even 14 A free executable for period finding (FINDPRIM.EXE) can also be downloaded from: http://users. pandora.be/nicvroom/progrm19.htm Shor's factorization algorithm 5 6 7 8 9 10 11 12 13 Figure 20.6 Values r of the order of X modulo N (x, N co-prime) for composites N = 15, 21, 33, 35, 39. The hashed bars correspond to odd values of r, the shaded bars correspond to r values