PALO ALTO, CA-October 30, 2002-The American Institute of Mathematics (AIM) today announced that it will convene world experts in number theoretic algorithms and cryptography early next year in Palo Alto. The brainstorming session is a response to the recent breakthrough in primality testing announced by computer scientist Manindra Agrawal, of the Indian Institute of Technology in Kanpur, and his students Neeraj Kayal and Nitin Saxena. The meeting, planned for March 24 - 28, 2003, will be organized by noted mathematicians Carl Pomerance, Hendrik Lenstra and Jonathan Pila, and will be funded by the National Science Foundation and AIM. Findings could have enormous relevance to the mathematics that powers secure internet transactions.
Agrawal's August 6 announcement of a fast method for detecting prime numbers caught the mathematical world by surprise. Prime numbers (for example, 2, 7, 17, and 101), are only divisible by themselves and 1. The new algorithm gives a quick way to tell if a very large number is prime.
"Experts have been thinking about this problem for many years. It's amazing how simple and elegant this solution is," said Brian Conrey, Executive Director of AIM. "Our goal at the upcoming workshop is to see if the mathematical ideas behind their algorithm can be used to solve other important problems. Their result will inspire new efforts on many related questions."
The new algorithm developed by Agrawal and his team is stunningly simple and scales remarkably well. Mathematicians are now wondering if other, to-date elusive, algorithms might have been overlooked. A particularly tantalizing goal is a fast method for determining the factors of large numbers. Some basic trial and error will lead you to find the factors of 689 - its prime factors are 13 and 53. But factoring much larger numbers is serious business, and a fast method for finding the factors of a large number could break some of the encryption schemes currently in use.
The RSA encryption scheme, used to ensure the privacy of many internet exchanges, relies on the assumption that no one knows a fast method of factoring integers having hundreds of digits, and is widely considered invulnerable to hackers. However, if someone were to find a fast factoring algorithm it would turn the internet world on its ear, and would force vendors of security products to use new encryption schemes.
At present, nobody has suggested a way to turn the new primality algorithm into a factoring algorithm. "It is important to examine every aspect of the problem," remarked Conrey. "There are some serious implications for national security if someone found a fast factoring algorithm, so this is something we will consider carefully at the workshop. We wouldn't want someone else to figure it out and keep it a secret."
"There are two things that could upset the way encryption is used today: advances in factoring, and quantum computer cryptoanalysis," said Victor S. Wheatman, Vice President and Research Area Director at Gartner Research in San Jose. "If this factoring research proves out, or if quantum computers soon demonstrate the ability to decrypt, confidence in today's public key-based algorithms will precipitously drop, and new methods will be needed."
"The new method found by Agrawal's team has already stimulated an enormous amount of work on some crucial questions," said Peter Sarnak, Chair of AIM's Scientific Board, and a professor in the Princeton Mathematics Department. "For the upcoming workshop we have assembled a group of exceptional mathematicians with great insight into this field. Pomerance and Lenstra have found ways to further simplify Agrawal's original work, and Pila is an expert on related number theoretic algorithms. We feel it is imperative to bring these three leaders together, along with Agrawal and his students and other top world authorities, to focus on these urgent questions - and to get some answers."
Although the meeting will not be open to the public, findings from the meeting will be available on the AIM website: http://www.aimath.org.
The need for a collaborative approach to mathematics
AIM is fast emerging as a world center for collaborative mathematics. Today, mathematics is flourishing because of a growing need to model complex phenomena and increased public awareness of its importance as the foundation for our technology-driven world. Thousands of mathematicians at hundreds of universities around the world are making seminal contributions to the subject. Whereas fifty years ago mathematical collaboration was relatively rare, today approximately half of all mathematical papers are written by multiple authors, with rich results for the field. Mathematics workshops, traditionally important in the development of mathematics, are emerging as crucial to continuing and extending this increased level of collaboration. AIM recently received a significant grant from the National Science Foundation for the express purpose of regularly convening focused mathematics workshops.
About the new primality testing algorithm
The algorithm is compact - only 12 lines of code. Some additional interesting tidbits:
About the National Science Foundation
The National Science Foundation(NSF) is the leading funding agency for pure and applied mathematics in the United States. For more information visit www.nsf.gov.
About the American Institute of Mathematics
The American Institute of Mathematics is a non-profit organization devoted to expanding the frontiers of mathematical knowledge and their applications, through focused research projects, sponsored workshops, and the development of a wide range of research tools made freely available over the internet. AIM is also involved in educational and outreach activities, especially those that further the integration of young people into mathematical research. AIM is headquartered in Palo Alto, California. For more information, visit http://www.aimath.org .