| |
| |
| Preface | |
| |
| |
| |
| Primes! | |
| |
| |
| |
| Problems and progress | |
| |
| |
| |
| Fundamental theorem and fundamental problem | |
| |
| |
| |
| Technological and algorithmic progress | |
| |
| |
| |
| The infinitude of primes | |
| |
| |
| |
| Asymptotic relations and order nomenclature | |
| |
| |
| |
| How primes are distributed | |
| |
| |
| |
| Celebrated conjectures and curiosities | |
| |
| |
| |
| Twin primes | |
| |
| |
| |
| Prime k-tuples and hypothesis H | |
| |
| |
| |
| The Goldbach conjecture | |
| |
| |
| |
| The convexity question | |
| |
| |
| |
| Prime-producing formulae | |
| |
| |
| |
| Primes of special form | |
| |
| |
| |
| Mersenne primes | |
| |
| |
| |
| Fermat numbers | |
| |
| |
| |
| Certain presumably rare primes | |
| |
| |
| |
| Analytic number theory | |
| |
| |
| |
| The Riemann zeta function | |
| |
| |
| |
| Computational successes | |
| |
| |
| |
| Dirichlet L-functions | |
| |
| |
| |
| Exponential sums | |
| |
| |
| |
| Smooth numbers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Number-Theoretical Tools | |
| |
| |
| |
| Modular arithmetic | |
| |
| |
| |
| Greatest common divisor and inverse | |
| |
| |
| |
| Powers | |
| |
| |
| |
| Chinese remainder theorem | |
| |
| |
| |
| Polynomial arithmetic | |
| |
| |
| |
| Greatest common divisor for polynomials | |
| |
| |
| |
| Finite fields | |
| |
| |
| |
| Squares and roots | |
| |
| |
| |
| Quadratic residues | |
| |
| |
| |
| Square roots | |
| |
| |
| |
| Finding polynomial roots | |
| |
| |
| |
| Representation by quadratic forms | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Recognizing Primes and Composites | |
| |
| |
| |
| Trial division | |
| |
| |
| |
| Divisibility tests | |
| |
| |
| |
| Trial division | |
| |
| |
| |
| Practical considerations | |
| |
| |
| |
| Theoretical considerations | |
| |
| |
| |
| Sieving | |
| |
| |
| |
| Sieving to recognize primes | |
| |
| |
| |
| Eratosthenes pseudocode | |
| |
| |
| |
| Sieving to construct a factor table | |
| |
| |
| |
| Sieving to construct complete factorizations | |
| |
| |
| |
| Sieving to recognize smooth numbers | |
| |
| |
| |
| Sieving a polynomial | |
| |
| |
| |
| Theoretical considerations | |
| |
| |
| |
| Recognizing smooth numbers | |
| |
| |
| |
| Pseudoprimes | |
| |
| |
| |
| Fermat pseudoprimes | |
| |
| |
| |
| Carmichael numbers | |
| |
| |
| |
| Probable primes and witnesses | |
| |
| |
| |
| The least witness for n | |
| |
| |
| |
| Lucas pseudoprimes | |
| |
| |
| |
| Fibonacci and Lucas pseudoprimes | |
| |
| |
| |
| Grantham's Frobenius test | |
| |
| |
| |
| Implementing the Lucas and quadratic Frobenius tests | |
| |
| |
| |
| Theoretical considerations and stronger tests | |
| |
| |
| |
| The general Frobenius test | |
| |
| |
| |
| Counting primes | |
| |
| |
| |
| Combinatorial method | |
| |
| |
| |
| Analytic method | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Primality Proving | |
| |
| |
| |
| The n - 1 test | |
| |
| |
| |
| The Lucas theorem and Pepin test | |
| |
| |
| |
| Partial factorization | |
| |
| |
| |
| Succinct certificates | |
| |
| |
| |
| The n + 1 test | |
| |
| |
| |
| The Lucas-Lehmer test | |
| |
| |
| |
| An improved n + 1 test, and a combined n[superscript 2] - 1 test | |
| |
| |
| |
| Divisors in residue classes | |
| |
| |
| |
| The finite field primality test | |
| |
| |
| |
| Gauss and Jacobi sums | |
| |
| |
| |
| Gauss sums test | |
| |
| |
| |
| Jacobi sums test | |
| |
| |
| |
| The primality test of Agrawal, Kayal, and Saxena (AKS test) | |
| |
| |
| |
| Primality testing with roots of unity | |
| |
| |
| |
| The complexity of Algorithm 4.5.1 | |
| |
| |
| |
| Primality testing with Gaussian periods | |
| |
| |
| |
| A quartic time primality test | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Exponential Factoring Algorithms | |
| |
| |
| |
| Squares | |
| |
| |
| |
| Fermat method | |
| |
| |
| |
| Lehman method | |
| |
| |
| |
| Factor sieves | |
| |
| |
| |
| Monte Carlo methods | |
| |
| |
| |
| Pollard rho method for factoring | |
| |
| |
| |
| Pollard rho method for discrete logarithms | |
| |
| |
| |
| Pollard lambda method for discrete logarithms | |
| |
| |
| |
| Baby-steps, giant-steps | |
| |
| |
| |
| Pollard p - 1 method | |
| |
| |
| |
| Polynomial evaluation method | |
| |
| |
| |
| Binary quadratic forms | |
| |
| |
| |
| Quadratic form fundamentals | |
| |
| |
| |
| Factoring with quadratic form representations | |
| |
| |
| |
| Composition and the class group | |
| |
| |
| |
| Ambiguous forms and factorization | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Subexponential Factoring Algorithms | |
| |
| |
| |
| The quadratic sieve factorization method | |
| |
| |
| |
| Basic QS | |
| |
| |
| |
| Basic QS: A summary | |
| |
| |
| |
| Fast matrix methods | |
| |
| |
| |
| Large prime variations | |
| |
| |
| |
| Multiple polynomials | |
| |
| |
| |
| Self initialization | |
| |
| |
| |
| Zhang's special quadratic sieve | |
| |
| |
| |
| Number field sieve | |
| |
| |
| |
| Basic NFS: Strategy | |
| |
| |
| |
| Basic NFS: Exponent vectors | |
| |
| |
| |
| Basic NFS: Complexity | |
| |
| |
| |
| Basic NFS: Obstructions | |
| |
| |
| |
| Basic NFS: Square roots | |
| |
| |
| |
| Basic NFS: Summary algorithm | |
| |
| |
| |
| NFS: Further considerations | |
| |
| |
| |
| Rigorous factoring | |
| |
| |
| |
| Index-calculus method for discrete logarithms | |
| |
| |
| |
| Discrete logarithms in prime finite fields | |
| |
| |
| |
| Discrete logarithms via smooth polynomials and smooth algebraic integers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Elliptic Curve Arithmetic | |
| |
| |
| |
| Elliptic curve fundamentals | |
| |
| |
| |
| Elliptic arithmetic | |
| |
| |
| |
| The theorems of Hasse, Deuring, and Lenstra | |
| |
| |
| |
| Elliptic curve method | |
| |
| |
| |
| Basic ECM algorithm | |
| |
| |
| |
| Optimization of ECM | |
| |
| |
| |
| Counting points on elliptic curves | |
| |
| |
| |
| Shanks-Mestre method | |
| |
| |
| |
| Schoof method | |
| |
| |
| |
| Atkin-Morain method | |
| |
| |
| |
| Elliptic curve primality proving (ECPP) | |
| |
| |
| |
| Goldwasser-Kilian primality test | |
| |
| |
| |
| Atkin-Morain primality test | |
| |
| |
| |
| Fast primality-proving via ellpitic curves (fastECPP) | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| The Ubiquity of Prime Numbers | |
| |
| |
| |
| Cryptography | |
| |
| |
| |
| Diffie-Hellman key exchange | |
| |
| |
| |
| RSA cryptosystem | |
| |
| |
| |
| Elliptic curve cryptosystems (ECCs) | |
| |
| |
| |
| Coin-flip protocol | |
| |
| |
| |
| Random-number generation | |
| |
| |
| |
| Modular methods | |
| |
| |
| |
| Quasi-Monte Carlo (qMC) methods | |
| |
| |
| |
| Discrepancy theory | |
| |
| |
| |
| Specific qMC sequences | |
| |
| |
| |
| Primes on Wall Street? | |
| |
| |
| |
| Diophantine analysis | |
| |
| |
| |
| Quantum computation | |
| |
| |
| |
| Intuition on quantum Turing machines (QTMs) | |
| |
| |
| |
| The Shor quantum algorithm for factoring | |
| |
| |
| |
| Curious, anecdotal, and interdisciplinary references to primes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Fast Algorithms for Large-Integer Arithmetic | |
| |
| |
| |
| Tour of "grammar-school" methods | |
| |
| |
| |
| Multiplication | |
| |
| |
| |
| Squaring | |
| |
| |
| |
| Div and mod | |
| |
| |
| |
| Enhancements to modular arithmetic | |
| |
| |
| |
| Montgomery method | |
| |
| |
| |
| Newton methods | |
| |
| |
| |
| Moduli of special form | |
| |
| |
| |
| Exponentiation | |
| |
| |
| |
| Basic binary ladders | |
| |
| |
| |
| Enhancements to ladders | |
| |
| |
| |
| Enhancements for gcd and inverse | |
| |
| |
| |
| Binary gcd algorithms | |
| |
| |
| |
| Special inversion algorithms | |
| |
| |
| |
| Recursive-gcd schemes for very large operands | |
| |
| |
| |
| Large-integer multiplication | |
| |
| |
| |
| Karatsuba and Toom-Cook methods | |
| |
| |
| |
| Fourier transform algorithms | |
| |
| |
| |
| Convolution theory | |
| |
| |
| |
| Discrete weighted transform (DWT) methods | |
| |
| |
| |
| Number-theoretical transform methods | |
| |
| |
| |
| Schonhage method | |
| |
| |
| |
| Nussbaumer method | |
| |
| |
| |
| Complexity of multiplication algorithms | |
| |
| |
| |
| Application to the Chinese remainder theorem | |
| |
| |
| |
| Polynomial arithmetic | |
| |
| |
| |
| Polynomial multiplication | |
| |
| |
| |
| Fast polynomial inversion and remaindering | |
| |
| |
| |
| Polynomial evaluation | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Research problems | |
| |
| |
| |
| Book Pseudocode | |
| |
| |
| References | |