rime number theorem" states that the number of primes not exceeding x is asymptotic to x/lnx. Actually, a finer approx- imation to (x) is x/(1nx 1). For reference, see, for instance, http://primes.utm.edu/howmany.shtml 5 Indeed, it is easily checked that multiplying two numbers with N and M decimals (or bits) requires N X M individual multiplications and N x M - - 1 additions of the resulting terms. The number of gates is thus O(N X M), or O(N2) for a squaring operation (N = M). 6 A complete list of prime factors up to N = 1000 is available at http://en.wikipedia.org/wiki/Table_ prime_factors 20.4 From order finding to factorization Table 20.2 Factorization of integers into primes up to N = 30. 3 X 7 2 x 32 22 x 7 2 x 7 23 X 3 2 x 5 3 x 5 mentally. This is because we have our multiplication tables memorized, which leaves out a list of the first prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, It only takes a few divisions to hit one or two numbers from such a short list. For greater numbers that can be entered into a pocket calculator or a computer spreadsheet, the problem of factorizing is also elementary. The basic approach consists of the routine of successively attempting to divide N by all known prime numbers lower than repeating such a trial division until complete prime factoring is obtained. Extensive lists of the known prime numbers, up to 15 million, are available on the Internet, making it possible to implement such a trial division algorithm. More practical and efficient algorithms exist, however, named after Pollard, William, Lenstra, Fermat, Dixon, and Shank, and also under different variants of the so-called "number field sieve."8 The most efficient one is the general number field sieve (GNFS) algorithm, which applies to numbers having more than 100 binary digits. It is not the point here to describe the GNFS algorithm and its variants, but only to mention that its complexity (the minimum computing program length, see Chapter 7) is defined by:9 (20.26) It can be shown that the bes