All of the mathematics required beyond basic calculus is developed “from scratch.” Moreover, the book generally alternates between “theory” and “applications”: one or two chapters on a particular set of purely mathematical concepts are followed by one or two chapters on algorithms and applications; the mathematics provides the theoretical underpinnings for the applications, while the applications both motivate and illustrate the mathematics. Of course, this dichotomy between theory and applications is not perfectly maintained: the chapters that focus mainly on applications include the development of some of the mathematics that is specific to a particular application, and very occasionally, some of the chapters that focus mainly on mathematics include a discussion of related algorithmic ideas as well.
The mathematical material covered includes the basics of number theory (including unique factorization, congruences, the distribution of primes, and quadratic reciprocity) and of abstract algebra (including groups, rings, fields, and vector spaces). It also includes an introduction to discrete probability theory—this material is needed to properly treat the topics of probabilistic algorithms and cryptographic applications. The treatment of all these topics is more or less standard, except that the text only deals with commutative structures (i.e., abelian groups and commutative rings with unity) — this is all that is really needed for the purposes of this text, and the theory of these structures is much simpler and more transparent than that of more general, non-commutative structures.
Access also available here: https://shoup.net/ntb/
Table of Contents
1 Basic properties of the integers
2 Congruences
3 Computing with large integers
4 Euclid's algorithm
5 The distribution of primes
6 Abelian groups
7 Rings
8 Finite and discrete probability distributions
9 Probabilistic algorithms
10 Probabilistic primality testing
11 Finding generators and discrete logarithms in Z∗p
12 Quadratic reciprocity and computing modular square roots
13 Modules and vector spaces
14 Matrices
15 Subexponential-time discrete logarithms and factoring
16 More rings
17 Polynomial arithmetic and applications
18 Finite Fields
19 Linearly generated sequences and applications
20 Algorithms for finite fields
21 Deterministic primality testing