11, or 17). The calculation of the six GCDs corresponding to the three solutions X1, x2, X3, namely, GCD(x1 1, N), GCD(x2 1, N), and GCD(x3 1, N), thus, makes it possible to factorize N completely. The lesson learnt from Theorem 1 and these two illustrative examples is that the knowledge of any single (nontrivial) solution of x2 = 1 mod N yields two factors of N. The complete factorization of N can, thus, be achieved by repeating the process with the remaining factors (call any of these N'), provided that for each we can find a solution of x2 = 1 mod N'. What is the computation cost of the algorithm used to determine the GCDs? There exist several possible answers to this question, depending on the algorithm choice and its implementation. It can be shown that for L digit numbers, the extended Euclidian algorithm complexity is of the order of O(L²) or better and, furthermore, that there exist other algorithms for which finding the GCD is reduced to O[L(In L)2 In In L]. The continued fraction expansion algorithm, which was described in Section 20.3, can be also implemented for this purpose but, as we have seen, its complexity is O(L³). Here, we may only retain that finding the GCD through the extended Euclidian algorithm is, at most, of the order of O(L²). While Theorem 1 enables one to factorize a given composite number N rapidly, it exclusively relies on prior knowledge of at least one nontrivial solution ofx2 = 1 mod N. But how can we get this knowledge? This is where the order-finding algorithm, which was described in Section 20.2, nicely comes to the rescue. As we have seen, given any integer X, such that 1<x<N-1, the order of X modulo N is the smallest number r for which xr = 1 mod N. In the case where r is even, let y = xr/12. We, thus, have y2 = 1 mod N, which shows that y is a solution of the Theorem 1 equation. If y # 1 mod N, then y is a nontrivial solution of the equation and, according to the theorem, GCD(y 1, N) = GCD(x/2 1, N) is a factor of N. In this case, the order- finding algorithm successfully y