# A Course in Computational Number Theory

###### David Bressoud and Stan Wagon
Publisher:
Key College
Publication Date:
2000
Number of Pages:
367
Format:
Hardcover
Series:
Textbooks in Mathematical Sciences
Price:
74.95
ISBN:
978-1930190108
Category:
General
[Reviewed by
David P. Roberts
, on
02/21/2001
]

The book under review, to be called CNT for short, "is designed to be a one-semester introduction to number theory." It is aimed at mathematically skilled upper-level undergraduates with access to Mathematica. I am impressed on many levels and am adopting CNT for my number theory course.

The mathematics in CNT. Number theory is traditionally divided into its elementary, algebraic and analytic parts. This book is in the elementary part. Direct contact with numbers is never lost.

Prime numbers play a central role in CNT, three related open-ended problems being given extensive treatment. The first problem is to find quick tests which determine, up to a very small doubt, whether a given number is prime. The second is to find fast rigorous methods to prove that a suspected prime is indeed prime. The third problem is to quickly factor composite numbers into primes. Several solutions are presented for each of these three problems, and the state of the art is surveyed.

Students following CNT will not be told what a number field is. Nor will they see more than a passing nod at the Riemann zeta function. Nonetheless, CNT emphasizes some parts of elementary number theory which are really the beginning of large algebraic and analytic theories. On the algebraic side, the text has extensive treatments of quadratic reciprocity, Pell's equation, and Gaussian primes. On the analytic side, there is an introduction to the distribution of primes and a description of the genesis of the quadratic sieve. All in all, the choice of topics is excellent.

The computational approach of CNT. The text aims to have students actually experience the computational approach to mathematics. There is a lot of narrative in the spirit of "Now we look at the first 1000 integers, and discover that..." Only after substantial preparation on a given topic are students exposed to theorems and their proofs.

Mathematicais blended into the text skillfully. For beginners, there is a practical introduction in an appendix. Throughout the text, brief Mathematica exchanges are regularly displayed, offering to students many elegant models of how to actually use Mathematica. It is not expected that the typical student will do serious programming in Mathematica, but there are many exercises aimed at students who do want to program.

Mathematica has many high level commands that correspond exactly to central topics in CNT. For example, Prime[n] works very quickly for n less than a billion, returning the nth prime in well less than a tenth of a second. A section of CNT explicitly raises and answers the question, how does Prime[n] work? In similar ways, different parts of the book correspond to the commands GCD, PowerMod, PrimeQ, FactorInteger, and so on.

Included with CNT is a CD containing yet more number-theoretic commands. These can be conveniently read into Mathematica all at once, on both PC and Macintosh platforms. The new commands are very simple to use and well-documented. Those that give complicated output format their output beautifully. Just about all topics in CNT are supported by commands on the CD. For example, commands corresponding to the very easiest topics include PascalTriangle, PythagoreanTriples and EratosthenesTable. Commands corresponding to more specialized topics include AliquotSequence, FullContinuedFraction, LucasCertificate, RSAEncode, RSADecode, PellSolve, and GaussianPrimePlot. The effect of all these commands is to render abstract operations immediately tangible.

The target audience of CNT. If students are to profit from CNT, they need to have both native mathematical talent and substantial previous mathematical experience. Good performance in a year of calculus and two more semester courses might be considered a reasonable minimum. It is not the specific content of these previous courses that is relevant, but rather the associated increase in mathematical maturity. We may lament that the pool of such students is small. A virtue of CNT is that it is truly aimed at the entire pool, not just the much smaller collection of students who are thinking about going on to graduate school in mathematics.

One way CNT is aimed at the entire pool is that it uses the common language of mathematical science, not the specialized language of pure mathematics. For example, the authors have made the tough choice of not requiring any sort of abstract algebra as a prerequisite, even though it would streamline the text at a number of points. So the text is intelligible just as much to computer science students as it is to math majors. Engineering students and physics majors are candidate students as well.

Another way CNT is aimed at the entire pool is that it is an exciting text in its own right. It is not just an assemblage of tools to be used in some way later, when the real excitement will supposedly kick in. Students following CNT will be impressed by the very long history of the subject, told in appealing snippets throughout the text. They will recognize that RSA encryption, presented so very clearly in CNT, is a serious real world application. They will appreciate that throughout the course they have been sitting atop an incredibly powerful computational engine. They will be pleased that they can understand and recognize the importance of the many unsolved problems mentioned in CNT.

The wealth of material in CNT is connected more thematically than logically. I would say that a thorough treatment of one-third of the material would make a very respectable semester course. The remaining two-thirds of the book could then serve as a resource for students to present individual projects.

David Bressoud and Stan Wagon each have reputations for writing excellent texts. This is their first joint book, and it fully met my high expectations.

David Roberts is an assistant professor of mathematics at University of Minnesota, Morris. His research often concerns computational aspects of algebraic number theory.