Chapter 1 Why Factor Integers? Suppose, for example, that two 80-digit1 numbers p and q have been proved prime . . . Suppose fur- ther, that the cleaning lady gives p and q by mistake to the garbage collector, but that the product pq is saved. How to recover p and q? It must be felt as a defeat for mathematics that, in these circum- stances, the most promising approaches are search- ing the garbage dump and applying mnemo-hypnotic techniques. H. W. Lenstra, Jr. [Len82] Introduction A modern reason for studying the problem of factoring integers is the cryptanalysis of certain public-key ciphers, such as the RSA system. We will explain public-key cryptography and its connection to factor- ing in the next section. The rest of the chapter discusses some older reasons for factoring integers. These include repunits, describing per- fect numbers, and determining the length of repeating decimals. We introduce the Cunningham Project, which has factored interesting numbers for more than a century. 1 The size of these primes would have to be doubled now due to the improvement in the speed of factoring algorithms since Lenstra wrote these words in 1982. 1
Previous Page Next Page