This book was published in the “ACM Distinguished Dissertations” series published by MIT Press. This reflects its high standing in the annual contest of doctoral dissertations in computer science and engineering; the contest is cosponsored by the publisher and ACM.

The primary area is analytic number theory, with important applications and related areas in cryptography, prime factorization, and probabilistic algorithms. According to the author, readers should know something about high-precision arithmetic from computer science, and elementary number theory, probability, and statistics from mathematics. They should also be familiar with the evaluation of integrals by residues; some use is also made of Stieltjes integrals.

It is easy to understand the excellent impression this dissertation made on the contest judges. Its style is outstandingly readable, and its contents are extremely elegant, both in the results presented and in their derivation.

The readability is insured by the various levels at which the author describes his results. Besides the Preface and the Introduction, where the background and present ideas are summarized, Bach gives a careful rundown in the beginning of each chapter of what the reader will encounter in each section of that chapter. The style of the technical presentation is a model of clarity as well.

There are two chapters in the book. The first, Explicit Bounds for Primality Testing, contains some refinements of the complexity of known algorithms. The second, The Generation of Random Factorizations, presents an algorithm for quickly producing random numbers and their prime factors.

The setting for the first chapter is an investigation of the efficiency of Miller’s algorithm [1] in testing whether a number is prime. The criterion used is that p is prime if and only if for all a prime to p, a ^{p - 1} ≡ 1 ( mod p ), and a ^{( p - 1 ) / 2} ≡ ∓ a ^{( p - 1 ) / 4} ≡ . . . ≡ ∓ ( mod p ). Thus, unlike Fermat’s criterion, Miller’s is necessary and sufficient.

Miller also proved that his algorithm runs in polynomial time (in the length of the input integer). To do this, he used a theorem of Ankeny [2], which is turn assumes the Extended Riemann Hypothesis (ERH). What our author does in this chapter is to develop sharper estimates than heretofore known for the constants involved in these asymptotic formulas.

In the second chapter, primality testing is taken as a primitive operation. Using it, the author presents an algorithm for generating large random numbers with certain conditions on their factors. This is of considerable importance in cryptographical applications, for example. More specifically, for a given fixed positive integer N, this algorithm provides as output the prime factors of an integer x, uniformly distributed on the interval N/2 < x ≤ N. In the same helpful spirit of the earlier chapter, the first and second sections of this chapter provide lucid outlines and heuristics of the technical material which follows.