Preface The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. . . . Neverthe- less we must confess that all methods that have been proposed thus far are either restricted to very spe- cial cases or are so laborious and prolix that even for numbers that do not exceed the limits of tables con- structed by estimable men, i.e. for numbers that do not yield to artificial methods, they try the patience of even the practiced calculator. . . . The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated. C. F. Gauss [Gau01, Art. 329] Factoring integers is important. Gauss said so in 1801. The problem of distinguishing prime numbers from composite numbers has been solved completely, both theoretically and practi- cally. We have made some progress on factoring composite integers, but it remains a difficult problem. Some mathematicians play a version of the television game show Jeopardy! with multiplication tables. Host Alex Trebek reads the ix
Previous Page Next Page