From the Preface:
This is the first volume of a projected two-volume set on algorithmic number theory, the design and analysis of algorithms for problems from the theory of numbers. This volume focuses primarily on those problems from number theory that admit relatively efficient solutions. The second volume will largely focus on problems for which efficient algorithms are not known, and applications thereof. We hope that the material in this book will be useful for readers at many levels, from the beginning graduate student to experts in the area. The early chapters assume that the reader is familiar with the topics in an undergraduate algebra course: groups, rings, and fields. Later chapters assume some familiarity with Galois theory. As stated above, this book discusses the current state of the art in algorithmic number theory. This book is not an elementary number theory textbook, and so we frequently do not give detailed proofs of results whose central focus is not computational. Choosing otherwise would have made this book twice as long. However, we firmly believe that a mere list of proved theorems is not particularly enlightening or useful. Therefore, we endeavor to prove as much as is feasible. Some proofs are left to the reader as exercises, with outlines suggested in Appendix A. And every theorem which is not proved in the text or left as an exercise has a reference in the "Notes" section that appears at the end of each chapter. This book is also not intended solely as a practical guide for those who wish to implement number-theoretic algorithms. The variety of architectures of modern machines, and the profusion of languages and operating systems, frequently make specific remarks on running times useless. On the other hand, computational theory without the influence of practice seems artificial. Thus, the "Notes" section of each chapter contains remarks on practical implementations of the algorithms discussed. In writing this book, we have found many opportunities to extend or refine known results. This is particularly true with regard to algorithms, many of whose running times were not completely worked out in the literature. As an alternative to listing all such improvements (which is clearly impractical), we give references to earlier results, such as are known to us, in the appropriate places.The book contains a large bibliography with references to more than 1800 papers and books. The BibTeX files for the bibliography of the book are available for your use without charge.
Preface 1. Introduction 1.1. Number theory and complexity. 1.2. Number theory and computation: a brief history. 1.3. Condensed history of the theory of computation. 1.4. Notes on Chapter 1 2. Fundamentals of Number Theory 2.1. Notation, definitions, and some computational problems. 2.2. More definitions. 2.3. Multiplicative functions and M\"obius inversion. 2.4. Notation: Big-O, Little-o, Big-Omega, Big-Theta. 2.5. Abel's identity and Euler's summation formula. 2.6. Asymptotic integration. 2.7. Estimating sums over primes. 2.8. Basic concepts of abstract algebra. 2.8.1. Semigroups, monoids, and groups. 2.8.2. Rings. 2.8.3. Fields. 2.9. Exercises. 2.10. Notes on Chapter 2. 3. A Survey of Complexity Theory. 3.1. Notation. 3.2. The notion of "step". 3.3. Language classes. 3.4. Reductions and NP-completeness. 3.5. Randomized complexity classes. 3.6. A formal computational model. 3.7. Other resources. 3.8. Parallel complexity classes. 3.9. Exercises. 3.10. Notes on Chapter 3. 4. The Greatest Common Divisor. 4.1. The Euclidean algorithm. 4.2. The Euclidean algorithm: worst-case analysis. 4.3. The extended Euclidean algorithm. 4.4. The Euclidean algorithm and continuants. 4.5. Continued fractions. 4.6. The least-remainder Euclidean algorithm. 4.7. The binary gcd algorithm. 4.8. Constructing a gcd-free basis. 4.9. Exercises. 4.10. Notes on Chapter 4. 5. Computing in Z/(n). 5.1. Basics. 5.2. Addition, subtraction, multiplication. 5.3. Multiplicative inverse. 5.4. The power algorithm. 5.5. The Chinese remainder theorem. 5.6. The multiplicative structure of (Z/(n))* 5.7. Quadratic residues. 5.8. The Legendre symbol. 5.9. The Jacobi symbol. 5.10. Exercises. 5.11. Notes on Chapter 5. 6. Finite Fields. 6.1. Basics. 6.2. The Euclidean algorithm. 6.3. Continued fractions. 6.4. Computing in k[X]/f. 6.5. Galois theory. 6.6. The structure of (k[X]/f)*. 6.7. Characters. 6.8. Exercises. 6.9. Notes on Chapter 6. 7. Solving Equations Over Finite Fields. 7.1. Square roots: group-theoretic methods. 7.2. Square roots: field-theoretic methods. 7.3. Computing d-th roots. 7.4. Polynomial factoring algorithms. 7.5. Other results on polynomial factoring. 7.6. Synthesis of finite fields. 7.7. Hensel's lemma. 7.8. Complexity-theoretic results. 7.9. Exercises. 7.10. Notes on Chapter 7. 8. Prime Numbers: Facts and Heuristics. 8.1. Some history. 8.2. The density of primes. 8.3. Sharp estimates and the Riemann hypothesis. 8.4. Primes in arithmetic progressions and the ERH. 8.5. Applications of the ERH. 8.6. Other conjectures about primes. 8.7. Extensions to algebraic numbers. 8.8. Some useful explicit estimates. 8.9. Exercises. 8.10. Notes on Chapter 8. 9. Prime Numbers: Basic Algorithms. 9.1. Primality proofs and Fermat's theorem. 9.2. Primality tests for numbers of special forms. 9.3. Pseudoprimes and Carmichael numbers. 9.4. Probabilistic primality tests. 9.5. ERH-based methods. 9.6. Primality testing using algebraic number theory. 9.7. Generation of "random" primes. 9.8. Prime number sieves. 9.9. Computing pi(x) and p(n). 9.10. Exercises. 9.11. Notes on Chapter 9. A. Solutions to Exercises.The projected contents of Volume II are given below:
Chapter 10: Solving Equations This chapter will cover algorithms to solve equations of a "Diophantine" nature. Examples include linear systems with integer coefficients, quadratic congruences, expressing integers as sums of squares, sparse linear systems, lattice algorithms, and applications. Chapter 11: Factoring Integers This chapter will discuss theoretical results about the factorization of numbers, and present factoring methods based on elementary number theory. Such methods include trial division, quadratic residue methods such as the quadratic sieve, and Pollard's "rho" method. In addition, it will discuss related methods based on algebraic number theory, such as class group algorithms and the number field sieve. Chapter 12: Discrete Logarithms This chapter will cover history and algorithms for the discrete logarithm problem. Methods include the "baby-step giant-step" method, the use of group structure, and index calculus methods. Special algorithms for finite fields of small characteristic will also be discussed. Chapter 13: Applications of Algebraic Geometry Many new algorithms in number theory are based on ideas from algebraic geometry. After a brief review of algebraic geometry, this chapter will discuss the elliptic curve factoring method (and the related p +- 1 methods), primality testing using elliptic curves, and methods to count points on algebraic varieties. It will also discuss ideas for reducing the randomness requirements of algorithms. Chapter 14: Reductions Among Number-Theoretic Problems This chapter will discuss what is known about the relative computational complexity of number theoretic problems: for example, what problems are equivalent in difficulty to factoring? Chapter 15: Applications This chapter will review the new area of "applied number theory". Examples include the RSA cryptosystem, methods for pseudo-random number generation, and error-correcting codes. Chapter 16: Open Problems We will close with a list of open problems in algorithmic number theory.