91261465571 The computation of p, took the equivalent of 30 CPU years, using 80 processors at 2.2 GHz clock cycle, and spread over 5 months of calendar time. The highest and yet unsolved challenge, RSA-2048, is a 2048-bit or 617-digit number. According to Eq. (20.27), its factorization is of the order O[f(N)] 22 8.5 x 10 151 It is clear that solving this last challenge will require even more substantial computing power and resources, along with new and significant progress in factorization algorithms, which may take a few decades. It is tempting to speculate that, by that time, factorization of such big numbers might be routinely performed by quantum computers through Shor's algorithm! Only history will tell. We now return to the core subject of this section, which is the connection between order finding and factoring. This connection requires two key theorems, which I am going successively to describe, comment, and illustrate with examples. It is assumed that N is a composite number of size L bits, and that X is an integer number such that 1xx N - 1. The notation GCD(n, m) corresponds to the greatest common divider between two integers n, m. THEOREM 20.1 If X is a nontrivial solution of x2 = 1 mod N, then either GCD(x - 1, N) or GCD(x + 1, N) is a factor of N; such a factor is computable in O(L²) operations. In the above, the two trivial solutions of x2 = 1 mod N to be discarded are X = 11 mod N corresponding to x = 1 and x = N By assumption, therefore, the solution x is in the range 1 <x<N - 1. We have x2 1 = 0 mod N, which shows that N divides by x2 1 = (x + 1)(x - 1), or, equivalently, that N has a common factor with either X - 1 or x + 1. We note that such a common factor cannot be N itself, since X - 1 <x+1 < N. Thus the factor is found by computing both GCD(x - 1, N) and GCD(x+1, N). I shall now illustrate Theorem 1 through two basic examples. 11 See http://mathworld.wolfram.com/RSANumber.html. 20.4 From order finding to factorization Table 20.3 Values of x2 = Z mod N for N = 35 and 1 <x<N-1. As a first ex