In this project we explore theoretical as well as practical methods for factoring large integers. One reason for interest in this problem is the Rivest-Shamir-Adleman cryptosystem, whose security relies on the difficulty of factoring. We are studying the quadratic sieve algorithm, the elliptic curve method, and the number field sieve. Parallel implementations and many improvements to these algorithms are being considered. The present state of the art is that one can factor any number up to about 115 digits in a reasonable time. Therefore, one should choose the product of two 100-digit primes as the smallest acceptable public key for the RSA cryptosystem.
Many factorizations are reported in a book by Wagstaff and four coauthors. The original copy of this book is maintained in a file at Purdue. It is updated continuously as new factorizations are obtained. Updates are published annually. The book, its updates, and especially its "Ten Most Wanted List" have inspired many people to factor large numbers with their computers and to invent new factoring algorithms.
CS Annual Report - 19 APR 1996