ields a determination of a factor of N. If y is a trivial solution, the algorithm fails, and the order-finding algorithm must be implemented again, using a different trial value for X. The same conclusion applies when r turns out to be odd. The fact that the algorithm may fail should not be perceived as an embarrassing weakness of the factoring endeavor. It just takes a finite number of order-finding trials (each of O(L³) to lead to a successful and conclusive step, and as many such trials to eventually achieve the full factorization. Actually, a second theorem shows that the convergence of the algorithm is strong. This theorem states: THEOREM 20.2 Given N, an odd composite integer with the factorization N = pak, where pi are prime numbers (ai integers), and given an integer X chosen at random in the interval [1, N - 1] and co-prime to N, the probability that r is even ly=x"/2 is a nontrivial solution of y2=1 mod N satisfies (20.29) 20.5 Shor's factorization algorithm This second theorem shows that the probability of successfully obtaining a factor of N rapidly increases with the number m of prime factors. In the most basic case m = 2 (as in the above-described RSA challenge), we have p > 1 - 1/22 = 0.75. This corresponds to a 25% probability of failure, which reduces to less than 0.5% in four successive trials! Since any composite is at least the factor of two primes, this failure probability actually represents an upper bound for all possible composites. Theorem 2 is also a very strong one: to implement the order-finding algorithm and find the factors of N if successful, we are allowed to choose at random any integer X, provided it be co-prime to N. The test is only a matter of calculating GCD(x, N), at a mere O(L²) cost. It is an academic issue to prove Theorem 2, which I shall not address here. The key lesson learnt is that the order-finding algorithm leads to efficient and rapid factorization of composite numbers. Basically, this whole description constitutes the essence and ingredients of Shor's factorizati