rs of CPU time. Including the preparation work, the total elapsed time was actually 2.2 months. Factorizing RSA-512 (previously RSA-155) required 160 workstations (175-400 MHz) and 120 personal computers (300-450 MHz) to run for 3.7 months, repre- senting a combined 35.7 years of CPU time. The total elapsed time was about 7.4 months. The two latest challenges, which were successfully met in 2003 and 2005, concerned RSA-576 and RSA-640, respectively. The latter took a combined 30 CPU years, repre- senting 5 months of elapsed time at a 2.2 GHz computing rate per machine! As for the RSA-2048, it may remain unchallenged not only in this current decade (2008-2020), but possibly over this century, as the estimates below illustrate. 7 See: www.rsa.com/rsalabs/node.asp?id=2093. Exact reproduction in the printed form of this book is not guaranteed. Classical and quantum cryptography The general method of "attack" for the factorization problem (and also finding log- arithms A from a = mA mod n) is known as GNFS (general number field sieve), or NFS. The word "sieve" comes from Erathosthenes (240 BC). This is the same person who estimated the circumference of the Earth (tens of centuries before the Earth was proven to be a sphere), based on the observation that, at the same time of year, the sun casts shadows with different angles for different latitudes. His nonintuitive "sieving algorithm" for sorting out prime numbers can be described as follows: "List all integers less than n and remove multiples of all primes less than or equal to the square root of n; the numbers that are left are the primes below n." The NFS algorithm is implemented two stages. 9 The first stage, called "sieving," requires moderate computation power (hence, the use of multiple personal computers and workstations in parallel), and leads to a set of equations referred to as the "matrix." The second stage requires a supercomputer with massive internal CPU-memory use (e.g., 0.8 Mbytes for RSA-140 and 3.2 Gbytes for RSA-155-RSA-512). Finding the solution o