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 diﬃcult problem. Some mathematicians play a version of the television game show Jeopardy! with multiplication tables. Host Alex Trebek reads the ix

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.