You are here

Factorization and Primality Testing

David M. Bressoud
Publication Date: 
Number of Pages: 
Undergraduate Texts in Mathematics
BLL Rating: 


[Reviewed by
Ana Momidic-Reyna
, on

Factorization and Primality Testing is one of the most concise and well-organized books on the subject. Written by an eminent mathematician, this book is an introduction to number theory built around different factorization techniques and primality testing algorithms, drawing from the history of mathematics, number theory, and theory of elliptic curves. It can also be used as a standard reference on the theory of prime numbers in a computational setting.

The book describes the Euclidean Algorithm, the Sieve of Eratosthenes, the Greek problem of finding the perfect numbers, crucial number theory observations made by Pierre de Fermat and important theorems by Euler, all of which have implications in today’s computational developments. The author presents several factorization techniques, such as Fermat's Algorithm, Pollard Rho, Pollard p–1, and he explores their applications.

This book helps reader understand why and how the Quadratic Sieve works and also describes later improvements, including the large prime refinement (which uses extra factorization with large primes) and Montgomery's refinement (which sieves over a shorter interval but with several different quadratic polynomials). In addition, the author proves Gauss’ theorems that answer the questions of when a modulus has a primitive root and exactly how many primitive roots there are. These results led to development of several primality tests (for moderately sized primes) by Edouard Lucas.

The Bháscara-Brouncker algorithm, the Brillhart-Morrison Continued Fraction algorithm, and the Lucas-Lehmer algorithm, as well as a primality test with continued fractions for Mersenne primes, are all explained in this book. Finally, there are two chapters on the arithmetic of elliptic curves, which is also used to study and implement factorization techniques and primality tests. This could be a great beginning for further study of elliptic curves, especially given that elliptic curve primality proving has become popular and is nowadays the most advanced deterministic primality testing for arbitrary numbers.

The author does an excellent job of presenting the theory behind the factoring algorithms, explaining how they have emerged, why they work, and how they can be implemented. His writing style is clear and concise. In addition to proving (most of) the theorems in the book, he discusses their applications, consequences, and roles in the development of the factorization techniques and primality tests. The exercises at the end of each chapter are engaging and challenging. The material must be taught in conjunction with a computer, however, and studying it requires that the computer algorithms in each chapter be implemented.

I can attest to the outstanding exposition of the material in this 1989 book, but one has to keep in mind that the field has progressed since then. Although my own interests include integer factoring algorithms, I would recommend a more current text for those who want to go deeply into that subject. On the other hand, the material in the book is still very important today. This book certainly belongs on the shelf of every undergraduate number theory student and of all readers who would like to begin learning this subject. A more interested reader should explore the many references and additionally to consult a more recent treatise.


The table of contents is not available.