Description
Book SynopsisIn 2002, Agrawal, Kayal, and Saxena answered a long-standing open question by presenting a deterministic test (the AKS algorithm) with polynomial running time that checks whether a number is prime or not. Rempe-Gillen and Waldecker introduce the aspects of number theory, algorithm theory, and cryptography that are relevant for the AKS algorithm and explain in detail why and how this test works.
Trade ReviewThe authors can be congratulated on making an important recent result accessible to a very wide audience." - Ch. Baxa,
Monatsh MathTable of Contents
- Preface
- Introduction
- Part I. Foundations
- Natural numbers and primes
- Algorithms and complexity
- Foundations of number theory
- Prime numbers and cryptography
- Part II. The AKS algorithm
- The starting point: Fermat for polynomials
- The theorem for Agrawal, Kayal, and Saxena
- The algorithm
- Open questions
- Solutions and comments to important exercises
- Bibliography
- List of symbols
- Index
