Prime Numbers

1 Primes!.- 1.1 Problems and progress.- 1.1.1 Fundamental theorem and fundamental problem.- 1.1.2 Technological and algorithmic progress.- 1.1.3 The infinitude of primes.- 1.1.4 Asymptotic relations and order nomenclature.- 1.1.5 How primes are distributed.- 1.2 Celebrated conjectures and curiosities.- 1.2.1 Twin primes.- 1.2.2 Prime k-tuples and hypothesis H.- 1.2.3 The Goldbach conjecture.- 1.2.4 The convexity question.- 1.2.5 Prime-producing formulae.- 1.3 Primes of special form.- 1.3.1 Mersenne primes.- 1.3.2 Fermat numbers.- 1.3.3 Certain presumably rare primes.- 1.4 Analytic number theory.- 1.4.1 The Riemann zeta function.- 1.4.2 Computational successes.- 1.4.3 Dirichlet L-functions.- 1.4.4 Exponential sums.- 1.4.5 Smooth numbers.- 1.5 Exercises.- 1.6 Research problems.- 2 Number-Theoretical Tools.- 2.1 Modular arithmetic.- 2.1.1 Greatest common divisor and inverse.- 2.1.2 Powers.- 2.1.3 Chinese remainder theorem.- 2.2 Polynomial arithmetic.- 2.2.1 Greatest common divisor for polynomials.- 2.2.2 Finite fields.- 2.3 Squares and roots.- 2.3.1 Quadratic residues.- 2.3.2 Square roots.- 2.3.3 Finding polynomial roots.- 2.3.4 Representation by quadratic forms.- 2.4 Exercises.- 2.5 Research problems.- 3. Recognizing Primes and Composites.- 3.1 Trial division.- 3.1.1 Divisibility tests.- 3.1.2 Trial division.- 3.1.3 Practical considerations.- 3.1.4 Theoretical considerations.- 3.2 Sieving.- 3.2.1 Sieving to recognize primes.- 3.2.2 Eratosthenes pseudocode.- 3.2.3 Sieving to construct a factor table.- 3.2.4 Sieving to construct complete factorizations.- 3.2.5 Sieving to recognize smooth numbers.- 3.2.6 Sieving a polynomial.- 3.2.7 Theoretical considerations.- 3.3 Pseudoprimes.- 3.3.1 Fermat pseudoprimes.- 3.3.2 Carmichael numbers.- 3.4 Probable primes and witnesses.- 3.4.1 The least witness for n.- 3.5 Lucas pseudoprimes.- 3.5.1 Fibonacci and Lucas pseudoprimes.- 3.5.2 Grantham's Frobenius test.- 3.5.3 Implementing the Lucas and quadratic Frobenius tests.- 3.5.4 Theoretical considerations and stronger tests.- 3.5.5 The general Frobenius test.- 3.6 Counting primes.- 3.6.1 Combinatorial method.- 3.6.2 Analytic method.- 3.7 Exercises.- 3.8 Research problems.- 4. Primality Proving.- 4.1 The n - 1 test.- 4.1.1 The Lucas theorem and Pepin test.- 4.1.2 Partial factorization.- 4.1.3 Succinct certificates.- 4.2 The n + 1 test.- 4.2.1 The Lucas-Lehmer test.- 4.2.2 An improved n + 1 test, and a combined n2 - 1 test.- 4.2.3 Divisors in residue classes.- 4.3 The finite field primality test.- 4.4 Gauss and Jacobi sums.- 4.4.1 Gauss sums test.- 4.4.2 Jacobi sums test.- 4.5 Exercises.- 4.6 Research problems.- 5 Exponential Factoring Algorithms.- 5.1 Squares.- 5.1.1 Fermat method.- 5.1.2 Lehman method.- 5.1.3 Factor sieves.- 5.2 Monte Carlo methods.- 5.2.1 Pollard rho method for factoring.- 5.2.2 Pollard rho method for discrete logarithms.- 5.2.3 Pollard lambda method for discrete logarithms.- 5.3 Baby-steps, giant-steps.- 5.4 Pollard p - 1 method.- 5.5 Polynomial evaluation method.- 5.6 Binary quadratic forms.- 5.6.1 Quadratic form fundamentals.- 5.6.2 Factoring with quadratic form representations.- 5.6.3 Composition and the class group.- 5.6.4 Ambiguous forms and factorization.- 5.7 Exercises.- 5.8 Research problems.- 6 Subexponential Factoring Algorithms.- 6.1 The quadratic sieve factorization method.- 6.1.1 Basic QS.- 6.1.2 Basic QS: A summary.- 6.1.3 Fast matrix methods.- 6.1.4 Large prime variations.- 6.1.5 Multiple polynomials.- 6.1.6 Self initialization.- 6.1.7 Zhang's special quadratic sieve.- 6.2 Number field sieve.- 6.2.1 Basic NFS: Strategy.- 6.2.2 Basic NFS: Exponent vectors.- 6.2.3 Basic NFS: Complexity.- 6.2.4 Basic NFS: Obstructions.- 6.2.5 Basic NFS: Square roots.- 6.2.6 Basic NFS: Summary algorithm.- 6.2.7 NFS: Further considerations.- 6.3 Rigorous factoring.- 6.4 Index-calculus method for discrete logarithms.- 6.4.1 Discrete logarithms in prime finite fields.- 6.4.2 Discrete logarithms via smooth polynomials and smooth algebraic integers.- 6.5 Exercises.- 6.6 Research problems.- 7. Elliptic Curve Arithmetic.- 7.1 Elliptic curve fundamentals.- 7.2 Elliptic arithmetic.- 7.3 The theorems of Hasse, Deuring, and Lenstra.- 7.4 Elliptic curve method.- 7.4.1 Basic ECM algorithm.- 7.4.2 Optimization of ECM.- 7.5 Counting points on elliptic curves.- 7.5.1 Shanks-Mestre method.- 7.5.2 Schoof method.- 7.5.3 Atkin-Morain method.- 7.6 Elliptic curve primality proving (ECPP).- 7.6.1 Goldwasser-Kilian primality test.- 7.6.2 Atkin-Morain primality test.- 7.7 Exercises.- 7.8 Research problems.- 8. The Ubiquity of Prime Numbers.- 8.1 Cryptography.- 8.1.1 Diffie-Hellman key exchange.- 8.1.2 RSA cryptosystem.- 8.1.3 Elliptic curve cryptosystems (ECCs).- 8.1.4 Coin-flip protocol.- 8.2 Random-number generation.- 8.2.1 Modular methods.- 8.3 Quasi-Monte Carlo (qMC) methods.- 8.3.1 Discrepancy theory.- 8.3.2 Specific qMC sequences.- 8.3.3 Primes on Wall Street?.- 8.4 Diophantine analysis.- 8.5 Quantum computation.- 8.5.1 Intuition on quantum Turing machines (QTMs).- 8.5.2 The Shor quantum algorithm for factoring.- 8.6 Curious, anecdotal, and interdisciplinary references to primes.- 8.7 Exercises.- 8.8 Research problems.- 9 Fast Algorithms for Large-Integer Arithmetic.- 9.1 Tour of "grammar-school" methods.- 9.1.1 Multiplication.- 9.1.2 Squaring.- 9.1.3 Div and mod.- 9.2 Enhancements to modular arithmetic.- 9.2.1 Montgomery method.- 9.2.2 Newton methods.- 9.2.3 Moduli of special form.- 9.3 Exponentiation.- 9.3.1 Basic binary ladders.- 9.3.2 Enhancements to ladders.- 9.4 Enhancements for gcd and inverse.- 9.4.1 Binary gcd algorithms.- 9.4.2 Special inversion algorithms.- 9.4.3 Recursive gcd for very large operands.- 9.5 Large-integer multiplication.- 9.5.1 Karatsuba and Toom-Cook methods.- 9.5.2 Fourier transform algorithms.- 9.5.3 Convolution theory.- 9.5.4 Discrete weighted transform (DWT) methods.- 9.5.5 Number-theoretical transform methods.- 9.5.6 Schönhage method.- 9.5.7 Nussbaumer method.- 9.5.8 Complexity of multiplication algorithms.- 9.5.9 Application to the Chinese remainder theorem.- 9.6 Polynomial arithmetic.- 9.6.1 Polynomial multiplication.- 9.6.2 Fast polynomial inversion and remaindering.- 9.6.3 Polynomial evaluation.- 9.7 Exercises.- 9.8 Research problems.- Book Pseudocode.- References.