s assumed. Then if we implement Shor's algorithm (namely without any prior knowledge of r), we have equal probabilities of measuring k = 0, 512, 1024, 1536, corresponding to the determinations = 0/2048, 512/2048, 1024/2048, 1536/2048. As we have seen, only the fourth one, = 1536/2048 = 3/4, is a convergent of Q. Thus, only one measurement in four pos- sibilities leads to a successful answer. If, on the other hand, our random selection is x = 4, 11, the probability distribution has only two peaks corresponding to the determi- nations = 0/2048 and = 1024/2048 = 1/2. Since none is a convergent of Q, the algorithm fails, and we must try it again with a different value of X. To summarize, the chances of randomly selecting the lucky values x = 2, 7, 8, 13 out of N - 3 = 12 possibilities in the interval x = [2, N - 2] are pl (1) = 4/12 = 1/3, and the chances that the output measurement leads to a convergent are P2 1/4. On the other hand, the chances of randomly selecting the "unlucky" values x = 4, 11 are p(1) 2/12 and the chances that the output measurement leads to a convergent are pl Over- all, the chances of the algorithm concluding successfully in a single run, based on any random selection of x are given by the probability indicator (20.35) 20.6 Factorizing N = 15 and other nontrivial composites Table 20.5 First group of composite numbers = pq(p, q = 3, 5, 7, 37) eligible for factorization, up to N = 1147, eliminating N = ab (as shaded). which gives here II = (1/3) X (1/4) + 0 = 1/12 = 8.3%. But the discussion does not end here. Indeed, this result actually assumes that the initial phase estimation is infinitely accurate (E 1). As we chose K = 2L + 1 + [log2[2 + 1/(2&)] = 11, cor- responding to an estimation success of at least p : 1 - E=3/4, the overall success chances in these global conditions are finally pll = (3/4) X (1/12) = 1/16 = 6.2%. As the register size K is increased, the chances of success asymptotically reach the limit II. The key conclusion of this discussion is that, regardless of register size, th