This book contains the papers presented at an instructional one-semester program held in the fall of 2000 at MSRI, Berkeley, on the topic of algorithmic number theory. All of the contributors are well-known number theorists with exceptional expository skills. Thus, the book provides an excellent introduction for the senior undergraduate student or beginning graduate student to enter into this branch of mathematics which offers interplay between number theory and algorithms of computer science.
Shortly after the MSRI program, Agrawal, Kayal and Saxena discovered a deterministic polynomial-time primality test using only basic undergraduate algebra. This breakthrough result appeared in the Annals of Mathematics in 2004 and the editors have attempted to include this work in the volume. It is discussed in Schoff's article titled “Four primality testing algorithms.”
There are twenty chapters in this book. The first two are introductory. They are articles by Hendrik Lenstra Jr., entitled “Solving the Pell equation” and by Joe Buhler and Stan Wagon, entitled “Basic algorithms in number theory.” The next eight articles provide overviews of several important topics, ranging from primality testing and factoring numbers to lattices, elliptic curves and algebraic number theory. The last ten chapters explore more deeply specific topics such as cryptography, modular forms and arithmetic geometry. Thus, the book addresses the reader at various levels.
Two mathematical themes form the background for a majority of the papers in the volume. The first is the topic of smooth numbers and the second is the study of lattices from an algorithmic standpoint.
A natural number is said to be y-smooth if all its prime factors are less than y. The distribution of smooth numbers in arithmetic progressions and in short intervals has emerged as a central topic in modern analytic number theory. Results obtained by using classical methods have found applications in primality testing and the factoring of numbers. Analysis of running times of many of these algorithms rely on results or conjectures about smooth numbers. Thus, this interplay of ideas has provided a fertile ground for the sprouting of new ideas and methods in both fields. For instance, the theory of smooth numbers enters in a fundamental way in at least seven of the chapters in this book.
The second theme of lattices pervades computational algebraic number theory, factorization of polynomials and the determination of Arakelov class groups. This topic is also related to elliptic curves and modular forms, both of which are playing a fundamental role in cryptography and other disciplines of an applied nature.
As the reader can judge by glancing at the table of contents, this book does not address readers of any single type. Rather, it addresses a spectrum of students, ranging from the undergraduate seeking an introduction to the subject to the graduate student and researcher looking for overviews of topics in an ever-expanding field. One thing any reader will appreciate from the book is the interplay of “pure mathematics” with “impure mathematics” and the important consequences of this admixture for the information age.
M. Ram Murty is Queen’s Research Chair in Mathematics and Philosophy at Queen’s University, Kingston, Ontario, Canada. He is also a Fellow of the Royal Society of Canada (FRSC) and the Indian National Science Academy (INSA). His research interests include number theory and Indian philosophy. He can be reached at firstname.lastname@example.org.
1. Solving Pell’s equation, Hendrik Lenstra
2. Basic algorithms in number theory, Joe Buhler and Stan Wagon
3. Elliptic curves, Bjorn Poonen
4. The arithmetic of number rings, Peter Stevenhagen
5. Fast multiplication and applications, Dan Bernstein
6. Primality testing, Rene Schoof
7. Smooth numbers: computational number theory and beyond, Andrew Granville
8. Smooth numbers and the quadratic sieve, Carl Pomerance
9. The number field sieve, Peter Stevenhagen
10. Elementary thoughts on discrete logarithms, Carl Pomerance
11. The impact of the number field sieve on the discrete logarithm problem in finite fields, Oliver Schirokauer
12. Lattices, Hendrik Lenstra
13. Reducing lattices to find small-height values of univariate polynomials, Dan Bernstein
14. Protecting communications against forgery, Dan Bernstein
15. Computing Arakelov class groups, Rene Schoof
16. Computational class field theory, Henri Cohen and Peter Stevenhagen
17. Zeta functions over finite fields, Daqing Wan
18. Counting points on varieties over finite fields, Alan Lauder and Daqing Wan
19. How to get your hands on modular forms using modular symbols, William Stein
20. Congruent number problems in dimension one and two, Jaap Top and Noriko Yui.