by Bob Bruen, Cipher Book Review Editor
Ribenboim, Paulo. The New Book of Prime Number Records. 3rd ed.
Springer Verlag. New York 1996. Index, chapter bibliographies, and
53 tables. 541p. $59.95
http://www.springer-ny.com/catalog/np/sep95np/DATA/0-387-94457-5.html
Prime numbers are at the root of current computer security techniques involving cryptography such that the level of security is approximately equivalent the difficulty of factoring. Some understanding of this problem is necessary for anyone interested in security and privacy, so I offer two good books that will provide enough background for most of us. Naturally each has pointers for further reading. Both books are written for mathematicians not computer security professionals, although both have sections on public keys and Reisel has Pascal code for various factorization methods. Appropriately this year is the first of the twin primes (1997,1999).
Having been available for a couple of years Reisel's book has already been deemed worthwhile. There are only seven chapters, but there are nine appendices. The chapters deal with fundamental problems; primes below a given limit, the distribution of primes, the recognition of primes and factoring. Factoring is broken into two chapters, one on classical method and one on modern methods. The seventh chapter is a short presentation on RSA. The second half of the book is split between the appendices (almost one hundred forty pages on the algebra necessary for the first half of the book) and the tables. The tables are composed of primes, factors in many formats, quadratic residues and formulas for cyclotomic polynomials. There is even an appendix devoted to elliptic curves.
He begins with a good introduction the concept of a prime number and the prime number theorem. Alongside this he describes the basic sieve of Eratosthenes in works, mathematical terms and Pascal code. The code for the book is available via ftp (ftp.nada.kth.se Num/riesel-comp.tar). This helpful approach is maintained throughout the book. It always increases my chance of understanding something when there are multiple methods of explanation.
Probably the two most important chapters are the one on the recognition of prime numbers and the modern factorization methods. In recognizing primes, he covers composite tests and primality tests, making the point that not all primality tests require factorization. The chapter on modern techniques naturally emphasizes computer applications. The many techniques presented, while not the complete set of techniques, are representative and instructive, and show the activity of the field today. Riesel's book certainly worth having for learning about primes numbers and how the are factored.
Paulo Ribenboim's book is in its third edition, attesting to its success. It is not just about prime number records, but it is a great history of prime numbers with the personalities involved in the development of the field. There are many number groups, series and methods named after the personalities, such as Fermat numbers, Mersenne numbers, Lucas pseudoprimes, Wilson primes and so on. All have their place in history and in working with prime numbers. While Ribenboim does not claim to be complete, he has collected an extensive amount of material on prime numbers which is quite readable.
As an example of its scope, this is one of the few sources that include an explanation Waring's problem. There are many prime number records in this book, for example, the largest (258,716 digits) in a table of the 28 largest, the largest palindromic prime (11,811 digits), the largest know prime in which all the digits are prime (3120 digits), the smallest primes with either 1000 or 2000 or 3000 digits, and the largest known prime with all digits either 1 or 0 (5856 digits).
Many more curiosities are in the book, but there is much more than just the records and the history. The six chapters also cover recognizing primes, functions defining primes, and the distribution of primes. The last chapter is about heuristic and probabilistic results about prime numbers. Ribenboim has a sense of humor expressed throughout the book that makes it entertaining while still being true to the mathematics. He even has haiku written by Basho included. This is a large compilation of research at the periphery of most people's interest, but it also illuminates the foundation of our electronic security and privacy. The explanations of prime numbers of all kinds are supported by an extensive bibliography for each chapter and lots of proofs in the chapters. It is great reference book for prime numbers with numerous tables, including the list of prime numbers up to 10,093. If you want to know about anything to do with prime numbers, this is the place to start.