t GNFS algorithm variant has a computational order of f(207) where k 2 log N is the binary size of the number N to be factorized. Thus, classical implementation of prime decomposition is subexponential, but superpolynomial in num- ber (bit) size. To show that the above conclusion is not innocuous, assume that the size is k = 100. We obtain from Eq. (20.27) the result O[f(N)] 2 4.7 x 10 39 For k = 1000, we obtain O[f(N)] 2 1.0 X 10112 For a classical computer having the computing power of one Giga (109) operations per second, or 3 X 1016 operations per year, just factoring a k = 100 number according to GNFS would require some 23 years, or, say, implementing about 100 such computers running in parallel for a duration of three months. We should now be convinced, if needed, that the factoring problem is nontrivial when it comes to relatively large numbers. This point is illustrated by the RSA challenge. 10 The company 7 See, for instance: http://en.wikipedia.org/wiki/List_of_prime_numbers www.math.utah.edu/~pa/math/ primelist.html; http://primes.utm.edu/lists/small/1000.txt;http://primes.utm.edu/lists/small/millions/. See http://en.wikipedia.org/wiki/Integer_factorization, 9 See tp://en.wikipedia.org/wiki/General_number_field_siev 10 See www.rsa.com/press_release.aspx?id=3520. Shor's factorization algorithm RSA offers substantial prizes for teams who may succeed in factoring composite num- bers of various sizes, i.e., given N, finding primes p, q such that N = pq. The latest challenge to be solved, called RSA_640, was reported on November 2005. 11 The number to be factorized had 193 digits, corresponding to 640 bits: = 418240490 043721 350750035888 567930 037 346 0228421 727 720161948 823206440 518081 504556346829 671 723 286782 437916272 838033415471 073 108 501919 548 529 007 337 724 822 783 525 742 386454 014691 736 602 477 652 346609, which decomposes into the two primes: 110852389 333 100 104 508 151212118 167 511579, =1900871281 664822113126851573935413975471896789968 515493666 638539 088 027 103 802 1044989571