**Introduction.**

**1. Simple Ciphers.**

The Shift Cipher. Reduction/Division Algorithm. The One-Time Pad. The Affine Cipher.

**2. Probability.**

Counting. Basic Ideas. Statistics of English. Attack on the Affine Cipher.

**3. Permutations.**

Cryptograms: Substitutions. Anagrams: Transpositions. Permutations. Shuffles. Block Interleavers.

**4. A Serious Cipher.**

The Vigenere Cipher. LCMs and GCDs. Kasiski Attack. Expected Values. Friedman Attack.

**5. More Probability.**

Generating Functions. Variance, Standard Deviation. Chebycheff's Inequality. Law of Large Numbers.

**6. Modern Symmetric Ciphers.**

Design Goals. Data Encryption Standard. Advanced Encryption Standard.

**7. The Integers.**

Divisibility. Unique Factorization. Euclidean Algorithm. Multiplicative Inverses. Computing Inverses. Equivalence Relations. The Integers mod

*m.*Primitive Roots, Discrete Logs.**8. The Hill Cipher.**

Hill Cipher Operation. Hill Cipher Attacks.

**9. Complexity.**

Big-Oh/Little-Oh Notation. Bit Operations. Probabilistic Algorithms. Comlexity. Subexponential Algorithms. Kolmogorov Complexity. Linear Complexity. Worst-Case versus Expected.

**10. Public-Key Ciphers.**

Trapdoors. The RSA Cipher. Diffie-Hellman Key Exchange. ElGamal Cipher. Knapsack Ciphers. NTRU Cipher. Arithmetica Key Exchange. Quantum Cryptography. U.S. Export Regulations.

**11. Prime Numbers.**

Euclid's Theorem. Prime Number Theorem. Primes in Sequences. Chebycheff's Theorem. Sharpest Asymptotics. Riemann Hypothesis.

**12. Roots Mod**

**.***p*

Fermat's Little Theorem. Factoring Special Expressions. Mersenne Numbers. More Examples. Exponentiation Algorithm. Square Roots mod

*p*. Higher Roots mod*p*.**13. Roots Mod Composites.**

Sun Ze's Theorem. Special Systems. Composite Moduli. Hensel's Lemma. Square-Root Oracles. Euler's Theorem. Facts about Primitive Roots. Euler's Criterion.

**14. Weakly Multiplicativity.**

Weak Multiplicativity. Arithmetic Convolutions. Möbius Inversion.

**15. Quadratic Reciprocity.**

Square Roots. Quadratic Symbols. Multiplicative Property. Quadratic Reciprocity. Fast Computation.

**16. Pseudoprimes.**

Fermat Pseudoprimes. Non-Prime Pseudoprimes. Euler Pseudoprimes. Solovay-Strassen Test. Strong Pseudoprimes. Miller-Rabin Test.

**17. Groups.**

Groups. Subgroups. Langrange's Theorem. Index of a Subgroup. Laws of Exponents. Cyclic Subgroups. Euler's Theorem. Exponents of Groups.

**18. Sketches of Protocols.**

Basic Public-Key Protocol. Diffie-Hellman Key Exchange. Secret Sharing. Oblivious Transfer. Zero-Knowledge Proofs. Authentication. e-Money, e-Commerce.

**19. Rings, Fields, Polynomials.**

Rings, Fields. Divisibility. Polynomial Rings. Euclidean Algorithm. Euclidean Rings.

**20. Cyclotomic Polynomials.**

Characteristics. Multiple Factors. Cyclotomic Polynomials. Primitive Roots. Primitive Roots mod

*p*. Prime Powers. Counting Primitive Roots. Non-Existence. Search Algorithm.**21. Random Number Generators.**

Fake One-Time Pads. Period of a pRNG. Congruential Generators. Feedback Shift Generators. Blum-Blum-Shub Generator. Naor-Reingold Generator. Periods of LCGs. Primitive Polynomials. Periods of LFSRs. Examples of Primitives. Testing for Primitivity.

**22. More on Groups.**

Group Homomorphisms. Finite Cyclic Groups. Infinite Cyclic Groups. Roots and Powers in Groups. Square Root Algorithm.

**23. Pseudoprimality Proofs.**

Lambda Function. Carmichael Numbers. Euler Witnesses. Strong Witnesses.

**24. Factorization Attacks.**

Pollard's Rho Method. Pollard's

*p*-1 Method. Pocklington-Lehmer Criterion. Strong Primes. Primality Certificates.**25. Modern Factorization Attacks.**

Gaussian Elimination. Random Squares Factoring. Dixon's Algorithm. Non-Sieving Quadratic Sieve. The Quadratic Sieve. Other Improvements.

**26. Finite Fields.**

Making Finite Fields. Examples of Field Extensions. Addition mod

*P*. Multiplication mod*P*. Multiplicative Inverses mod*P*.**27. Discrete Logs.**

Baby-Step Giant-Step. Pollard's Rho Method. The Index Calculus.

**28. Elliptic Curves.**

Abstract Discrete Logarithms. Discrete Log Ciphers. Elliptic Curves. Points at Infinity. Projective Elliptic Curves.

**29. More on Finite Fields.**

Ideals in Commutative Rings. Ring Homomorphisms. Quotient Rings. Maximal Ideals and Fields. More on Field Extensions. Frobenius Automorphism. Counting Irreducibles. Counting Primitives.

**Appendices.**

Sets and Functions. Searching, Sorting. Vectors. Matrices. Stirling's Formula.

**Tables.**

Factorizations under 600. Primes below 10,000. Primitive Roots under 100.

**Bibliography.**

**Answers to Selected Exercises.**

**Index.**