News Release

Banking on Mathematics: The Importance of Prime Factorization Sieves

November 4, 1996

For more information, please contact: Allyn Jackson, telephone 401-455-4109; fax 401-331-3842; e-mail axj@ams.org.

When you slip your ATM card into a cash machine, you are relying on a sophisticated cryptographic system. This system is designed so that even if an electronic "snooper" sees the communication between the ATM machine and the bank, the information would be useless because it is locked up in a code so tough that even the most powerful standard computers could not crack it in a reasonable time. If those stakes seem high, imagine what is riding on the codes that encrypt sensitive military communications, when not just money but lives are on the line.

Just how secure are these codes? Many of them rely on the difficulty of finding the prime factors of very large numbers. For example, a computer has no trouble finding that the prime factorization of 1443 is 37 x 13 x 3, but a 200-digit number is a different story. To have a realistic understanding of the security of codes, one must know the state of the art in methods for factoring large numbers.

Back in 1976 a group of mathematicians published a 129-digit "challenge" number, and estimates were that a factorization would not be found for millions of years. Confidence in current day codes was badly shaken when in 1994 a group of mathematicians factored the number with a network of computers that worked on the problem for about 8 months. The number was factored using a method known as the "quadratic sieve," which was developed in 1981 by Carl Pomerance, the author of the article "A Tale of Two Sieves", which appears in the January 1997 issue of the Notices of the AMS. Pomerance is one of the top experts in the field.

Effective methods for factoring large numbers require razor-sharp efficiency to cut computing time, as well as sophisticated understanding of patterns in and relationships among numbers. The mathematical investigation of prime factorizations has consumed the attention of many mathematicians, going back to the time of Euclid and continuing up to the present day.

The "quadratic sieve" collects tiny bits of information which are found by systematically sifting through a vast number of consecutive values of a quadratic polynomial. These bits of information are then combined in a huge matrix to find the prime factors of the given number. In the article, Pomerance also examines another similar method, the "number field sieve", which was discovered in 1988 by John Pollard. Each sieve works better than the other for certain numbers, and together they form a potent tool for factoring large numbers.

"A Tale of Two Sieves" describes the development of these two sieves while providing many insights into the development of this important field of mathematics.

Founded in 1888 to further mathematical research and scholarship, the 30,000-member AMS fulfills its mission through programs and services that promote mathematical research and its uses, strengthen mathematical education, and foster awareness and appreciation of mathematics and its connections to other disciplines and everyday life.