An Introduction to Number Theory with Cryptography

Citation

Kraft, J. S., & Washington, L. C. (2018). An Introduction to Number Theory with Cryptography (2nd ed.). Chapman & Hall/CRC.

Chapter Summary

The book has 21 chapters and two appendices. Each chapter ends with chapter highlights and a problems section that is divided into exercises, projects, computer explorations and answers to "Check Your Understanding" questions, although not every chapter has all four parts. The publisher describes the second edition as moving some basic pre-RSA cryptography into an earlier chapter, so that cryptography can be taught right after congruences.

Chapter 1: Introduction

A preview of the four themes of the book: Diophantine equations, modular arithmetic, primes and their distribution, and cryptography.

Chapter 2: Divisibility

Starts with divisibility, Euclid's theorem on the infinitude of primes and Euclid's original proof, then the Sieve of Eratosthenes and the division algorithm (with a cryptographic application). The chapter continues with the greatest common divisor, the Euclidean algorithm and its extended form, other bases, and Fermat and Mersenne numbers.

Chapters 3–4: Linear Diophantine Equations; Unique Factorization

Chapter 3 solves ax + by = c and treats the postage stamp problem. Chapter 4 begins from the starting point of factorization, proves the Fundamental Theorem of Arithmetic and discusses how Euclid approached it.

Chapter 5: Applications of Unique Factorization

Uses unique factorization for a series of results: irrationality proofs (including four more proofs that the square root of 2 is irrational), the rational root theorem, Pythagorean triples, differences of squares, the prime factorization of factorials, and the Riemann zeta function, including the divergence of the sum of 1/p over primes.

Chapter 6: Congruences

Definitions and examples, modular exponentiation, divisibility tests, linear congruences, the Chinese Remainder Theorem, fractions mod m, and the problem of placing queens on a chessboard.

Chapter 7: Classical Cryptosystems

The first cryptography chapter: shift and affine ciphers, Vigenère ciphers, transposition ciphers, stream ciphers (the one-time pad and linear feedback shift registers), block ciphers, secret sharing and the generation of random numbers.

Chapter 8: Fermat, Euler, and Wilson

The three classical theorems, each in its own section, the classical results on which RSA and primitive roots depend.

Chapter 9: RSA

RSA encryption and digital signatures.

Chapter 10: Polynomial Congruences

Polynomials mod primes, solutions modulo prime powers and composite moduli.

Chapter 11: Order and Primitive Roots

Orders of elements (with Fermat and Mersenne numbers), primitive roots, decimals (including Midy's theorem), card shuffling, the discrete log problem (baby step–giant step and index calculus) and a proof that primitive roots exist.

Chapter 12: More Cryptographic Applications

Diffie–Hellman key exchange, coin flipping over the telephone, mental poker and the ElGamal public key cryptosystem.

Chapter 13: Quadratic Reciprocity

Squares and square roots mod primes, computing square roots mod p, quadratic equations, the Jacobi symbol and a proof of quadratic reciprocity.

Chapter 14: Primality and Factorization

Trial division and Fermat factorization, then primality testing (pseudoprimes, the Pocklington–Lehmer test, the AKS test, and tests for Fermat and Mersenne numbers) and factorization (x² ≡ y², factoring with RSA exponents, Pollard's p − 1 method, the quadratic sieve), and a return to coin flipping.

Chapters 15–17: Geometry of Numbers; Arithmetic Functions; Continued Fractions

Chapter 15 covers Minkowski's theorem, sums of two and four squares and Pell's equation, with Bhāskara's chakravala method. Chapter 16 treats perfect numbers and multiplicative functions. Chapter 17 develops continued fractions, from rational approximation through periodic expansions and square roots of integers to some irrational numbers.

Chapters 18–19: Gaussian Integers; Algebraic Integers

Chapter 18 builds complex arithmetic, Gaussian irreducibles, a division algorithm and unique factorization, with applications to sums of two squares, Pythagorean triples and y² = x³ − 1. Chapter 19 moves to quadratic fields and algebraic integers, units, the rings Z[√−2] and Z[√3] (with the Lucas–Lehmer test), and non-unique factorization.

Chapters 20–21: The Distribution of Primes; Epilogue: Fermat's Last Theorem

Chapter 20 covers Bertrand's postulate and Chebyshev's approximate prime number theorem. Chapter 21 is an epilogue on Fermat's Last Theorem, introducing elliptic curves and modularity.

Appendices

Appendix A, Supplementary Topics: what a proof is (with proof by contradiction), geometric series, mathematical induction, Pascal's triangle and the binomial theorem, Fibonacci numbers and matrices. Appendix B gives answers and hints for odd-numbered exercises.

Key Concepts

Chapters 1–6: Foundations

• Euclidean algorithm: computing greatest common divisors, with an extended form that produces the coefficients needed for Diophantine equations and modular inverses.
• Unique factorization: every integer is a product of primes in essentially one way, the basis for the applications in Chapter 5.
• Congruence and the Chinese Remainder Theorem: arithmetic modulo m and the combination of congruences with different moduli.

Chapters 7–9 and 12: Cryptography

• Classical ciphers: shift, affine, Vigenère, transposition, stream and block ciphers, with secret sharing and random number generation.
• RSA: public-key encryption and digital signatures built on Euler's theorem.
• Diffie–Hellman and ElGamal: key exchange and public-key encryption based on the discrete log problem.

Chapters 10–14: Roots, Reciprocity, Primality

• Primitive roots and the discrete log problem: elements whose powers run through all units mod p, and the problem of recovering the exponent.
• Quadratic reciprocity and the Jacobi symbol: deciding whether numbers are squares modulo primes and composite numbers.
• Pseudoprimes and the AKS test: composites passing Fermat-type tests, and a polynomial-time primality test.

Chapters 15–21: Further Topics

• Minkowski's theorem: a geometric tool for proving results on sums of squares.
• Continued fractions and Pell's equation: rational approximation and a classical Diophantine equation.
• Gaussian and algebraic integers: rings of complex or algebraic numbers in which factorization is studied, including cases where it is not unique.

Critical Analysis

Strengths

• Cryptography integrated rather than appended. Cryptography appears in chapters 1, 7, 9, 12 and 14, interleaved with the theory it uses: classical ciphers after congruences, RSA after Euler's theorem, discrete logs after primitive roots, and factorization methods in the primality chapter. The publisher highlights increased cryptography coverage in this edition.
• A great deal of practice material. The publisher counts over 800 exercises, projects and computer explorations, with "Check Your Understanding" questions for instant feedback and answers and hints for odd-numbered problems. Each chapter's problems are divided into exercises, projects and computer explorations.
• Support for beginners. The appendices on what a proof is, induction, geometric series, the binomial theorem and matrices gather prerequisites in one place. The publisher describes the book as accessible to advanced high school students and suitable for independent study, and S. V. Nagaraj's review of the first edition (2014, hosted by the IACR) calls it well written and highly readable, with supplementary material helpful for self-learning.
• Room to go beyond the standard course. Geometry of numbers, Gaussian and algebraic integers, the distribution of primes and an epilogue on Fermat's Last Theorem give an instructor options after the core, and the publisher notes a few more advanced topics for students who want to explore beyond the traditional curriculum.

Limitations

• More than a semester. At about 600 pages (the publisher's figure) and 21 chapters, the book cannot be covered fully in one term, so instructors and self-studiers have to select.
• Narrow cryptography coverage. Cryptography in the book is number-theoretic: ciphers, RSA, discrete-log systems, key exchange, coin flipping and mental poker. Elliptic curves appear only in the Fermat's Last Theorem epilogue, so readers wanting elliptic-curve cryptography or protocol security will need another text.
• The epilogue is a survey. Chapter 21 has three sections (introduction, elliptic curves, modularity) so it explains the ideas around the proof of Fermat's Last Theorem without proving them.
• Answers only to odd-numbered exercises. Solutions to the remaining exercises are not given in the book, which matters for self-study.
• Level rises at the end. Chapters 18 and 19 on Gaussian and algebraic integers introduce ring-theoretic ideas such as units and non-unique factorization, and a student who has not met abstract algebra may find these chapters a step up.

Where It Fits in the Course

Within the number theory books on this site, Kraft and Washington is the one that treats classical number theory and modern cryptography together. Burton's Elementary Number Theory is the closest classical alternative: it follows a similar route to quadratic reciprocity with historical sections on the mathematicians involved, and the choice between them is largely whether to prefer that historical thread or cryptographic and computational applications. For readers new to proofs, Silverman's A Friendly Introduction to Number Theory is a gentler start built on experiment and conjecture, and Robin Wilson's Number Theory: A Very Short Introduction is a compact overview that also reaches public-key cryptography.

For further reading, Hardy and Wright's An Introduction to the Theory of Numbers is a classic treatise on elementary and analytic number theory, and Ireland and Rosen's A Classical Introduction to Modern Number Theory is a graduate text that assumes abstract algebra. The last chapters of Kraft and Washington (Gaussian integers, algebraic integers, the distribution of primes) are a bridge to both.

How to Use This Book

The publisher designs the book for sophomore, junior and senior undergraduates, and says it is also accessible to advanced high school students and appropriate for independent study. The site lists some experience with proofs and basic algebra as the prerequisite; Appendix A covers what a proof is, induction and the binomial theorem for readers who need a refresher.

A practical plan:

• Core number theory: Chapters 2 to 6 (divisibility, linear Diophantine equations, unique factorization, congruences), then Chapters 8, 11 and 13 (Fermat, Euler and Wilson; primitive roots; quadratic reciprocity).
• Cryptography track: Chapter 7 right after Chapter 6, RSA in Chapter 9 after Chapter 8, and Chapters 12 and 14 after the primitive roots and reciprocity material they draw on.
• Optional: Chapter 10 on polynomial congruences, Chapters 15 to 17 for geometry of numbers, arithmetic functions and continued fractions, and Chapters 18 to 21 for algebraic and analytic extensions.
• Practice: use the "Check Your Understanding" questions as you read, work the odd-numbered exercises with the answers at the back, and use the computer explorations with a computer algebra system for the factorization and primality tests.