ition of Shor's algorithm, the end result is a prime decomposition of two factors of N, according to N = pa paz M. In the case where M > 1, the "preamble" tests may be implemented for the possibility of trivial factoriza- 13 As a matter of fact, given r being even, the test xr/2 # 1 mod N does not need to be performed, as this condition is implicitly verified should x be selected from the interval [2, N - 1], or x # 1. This is because r is, by definition, the smallest integer verifying xr = 1 mod N. Since r is even, then r/2 is an integer. Then if we had xr/2 = 1 mod N with x # 1, the period of x would be r/2 and not r, which proves the point. 20.6 Factorizing N = 15 and other nontrivial composites tion. As applicable, Shor's algorithm may otherwise be called upon again to factorize M, and SO on until we obtain the full prime-factor decomposition = Factorizing N = 15 and other nontrivial composites In this section, I shall consider illustrative examples of Shor's factorization algorithm, using nontrivial composite cases (the notion of trivial composites will be specified further down). This will also show how one can simplify the inverse Fourier transform operation (FT+) in the quantum phase-estimation circuit, and estimate the probability distribution function of the phase measurement. Assume, for instance, the composite number N = 15. We must set L = [log2 N1 = 4 for the size of the second or target register, and for an error probability of at most E = 0.25, we must also set K = 2L + 1 + [log2[2 + 1/(2s)]] = 11 for the size of the first or control register. Thus, M = 2K = 2 11 = 2048. We then select "at random" from the interval [2, N - 2] the value x = 8, which meets the requirement of being co-prime to N. The qubit tensor input to the phase-estimation circuit in Fig. 20.3 is 1/1/1 = 10) Eq. (20.18). After passing through the Hadamard gate, it is transformed into (Eq. (20.19)): "="=" (20.30) After application of the controlled-UJ gate, we obtain the state (Eq. (20.20)): +15)|8) |1)|8) + + ||2>|4) |6)|4) +17)12