, (b) an L-qubit modular-exponentiation circuit (Ui), and (c) a K-qubit inverse Fourier transform circuit (FT+). Since K = 2L + 1 + [log2[2 + 1/(2s)]], given E the number of required gates in case (a) is of the order O(L), and in case (c) it is of the order O(K² = O(L²), as established in Chapter 19. The modular exponentiation in case (c) requires a number of gates of the order of O(L³). This is explained by the fact that computing |xj mod N), with j=0,1...2K, requires up to - 1 modulo N squaring operations (x21 x2x-1=(x2x-z), with each squaring operation having a cost of O(K² gates, resulting in an overall cost of O(K3 = O(L³) gates. Finally, the con- tinued fraction expansion, which is to be implemented with a classical computer, has a cost of O(L³) elementary operations. This is because the algorithm takes L split-and-invert steps, since S, r are L-bit integers, each of these steps requiring a number of basic arithmetic operations of the order O(L²) (see Appendix R, namely, the operations Un = 1/(un-1 - an-1) and the validation test 1/29 - A in Table R1). The key conclusion is that the order-finding algorithm has a complexity of O(L³) and, therefore, can be run in polynomial time. From order finding to factorization In this section, we describe how the quantum order-finding algorithm makes it possible to factorize composite numbers into primes, a problem also known as prime decomposition. Before going into the mathematical detail of the description, it is useful to outline the problem of factorizing composite numbers and its difficulty, as viewed from a classical computation perspective. It is a fundamental property that all integer numbers can be uniquely generated by products of prime numbers and their powers. This is illustrated in Table 20.2 for numbers up to N = 30.6 By definition, a composite number is a product of at least two prime numbers. For numbers up to a few hundreds, the task of factorizing can be performed The number of primes less than x corresponds to the heuristic function called (x). The "p