Making, Breaking Codes: An Introduction to Cryptology published by Prentice-Hall, ISBN 0-13-030369-0.
Now in a second corrected printing
  1. Simple Ciphers
    1. The Shift Cipher
    2. Reduction/Division Algorithm
    3. The One-Time Pad
    4. The Affine Cipher
  2. Probability
    1. Counting
    2. Basic Ideas
    3. Statistics of English
    4. Attack on the Affine Cipher
  3. Permutations
    1. Substitutions
    2. Transpositions
    3. Permutations [...through here by Sept 30]
    4. Shuffles ...Optional
    5. Block Interleavers ...Optional
  4. A Serious Cipher
    1. The Vigenere Cipher ...Optional (but important!)
    2. LCMs and GCDs
    3. Kasiski Attack ... Optional
    4. Expected Values
    5. Friedman Attack ...Optional (but important!)
  5. More Probability
    1. Generating Functions [...through here by Oct 16]
    2. Variance, Standard Deviation ... Optional
    3. Chebycheff's Inequality ... Optional
    4. Law of Large Numbers ... Optional
  6. Modern Symmetric Ciphers ... Optional
    1. Design Goals
    2. Data Encryption Standard
    3. Advanced Encryption Standard
  7. The Integers
    1. Divisibility
    2. Unique Factorization
    3. Euclidean Algorithm
    4. Multiplicative Inverses
    5. Computing Inverses [...through here by Oct 21]
    6. Equivalence Relations
    7. The Integers mod m
    8. Primitive Roots, Discrete Logs
  8. The Hill Cipher ... Optional
    1. Hill Cipher Operation
    2. Hill Cipher Attacks
  9. Complexity ... Optional
    1. Big-Oh/Little-Oh Notation
    2. Bit-Operations
    3. Probabilistic Algorithms
    4. Complexity
    5. Subexponential Algorithms
    6. Kolmogorov Complexity
    7. Linear Complexity
    8. Worst-Case versus Expected
  10. Public-Key Ciphers
    1. A Little History
    2. Trapdoors
    3. The RSA Cipher
    4. Diffie-Hellman Key Exchange
    5. ElGamal Cipher [...through here by Oct 28]
    6. Knapsack Ciphers ... Optional
    7. NTRU Cipher ... Optional
    8. Arithmetica Key Exchange ... Optional
    9. Quantum Cryptography ... Optional
    10. U.S. Export Regulations ... Optional
  11. Prime Numbers ... Optional
    1. Euclid's Theorem
    2. Prime Number Theorem
    3. Primes in Sequences
    4. Chebycheff's Theorem
    5. Sharpest Asymptotics
    6. Riemann Hypothesis
  12. Roots mod p
    1. Fermat's Little Theorem
    2. Factoring Special Expressions
    3. Mersenne Numbers
    4. More Examples
    5. Exponentiation Algorithm
    6. Square Roots mod p
    7. Higher Roots mod p [...through here by Nov 6]
  13. Roots Mod Composites delayed: after Pseudoprimes...
    1. Sun Ze's Theorem
    2. Special Systems
    3. Composite Moduli
    4. Hensel's Lemma
    5. Square-Root Oracles
    6. Euler's Theorem
    7. Facts about Primitive Roots
    8. Euler's Criterion
  14. Weak Multiplicativity ... Optional
    1. Weak Multiplicativity
    2. Arithmetic Convolutions
    3. Mobius Inversion
  15. Quadratic Reciprocity ... Optional
    1. Square Roots
    2. Quadratic Symbols
    3. Multiplicative Property
    4. Quadratic Reciprocity
    5. Fast Computation
  16. Pseudoprimes
    1. Fermat Pseudoprimes
    2. Non-Prime Pseudoprimes
    3. Euler Pseudoprimes ... Optional
    4. Solovay-Strassen Test ... Optional
    5. Strong Pseudoprimes
    6. Miller-Rabin Test [...through here by Nov 13]
  17. Groups
    1. Groups
    2. Subgroups
    3. Lagrange's Theorem
    4. Index of a Subgroup
    5. Laws of Exponents
    6. Cyclic Subgroups
    7. Euler's Theorem
    8. Exponents of Groups
  18. Sketches of Protocols
    1. Basic Public-Key Protocol
    2. Diffie-Hellman Key Exchange
    3. Secret Sharing
    4. Partial disclosure of secrets
    5. Oblivious Transfer
    6. Zero-Knowledge Proofs
    7. Authentication
    8. e-Money, e-Commerce
  19. Rings, Fields, Polynomials
    1. Rings, Fields
    2. Divisibility
    3. Polynomial Rings
    4. Euclidean Algorithm
    5. Euclidean Rings
  20. Cyclotomic Polynomials
    1. Characteristics
    2. Multiple Factors
    3. Cyclotomic Polynomials
    4. Primitive Roots
    5. Primitive Roots mod p
    6. Prime Powers
    7. Counting Primitive Roots
    8. Non-Existence
    9. Search Algorithm
  21. Random Number Generators
    1. Fake One-Time Pads
    2. Period of a pRNG
    3. Congruential Generators
    4. Feedback Shift Generators
    5. Blum-Blum-Shub Generator
    6. Naor-Reingold Generator
    7. Periods of LCGs
    8. Primitive Polynomials
    9. Periods of LFSRs
    10. Examples of Primitives
    11. Testing for Primitivity
    12. Counting Primitives
  22. More on Groups ... Optional
    1. Group Homomorphisms
    2. Finite Cyclic Groups
    3. Infinite Cyclic Groups
    4. Roots and Powers in Groups
    5. Square Root Algorithm
  23. Pseudoprimality Proofs ... Optional
    1. Lambda Function
    2. Carmichael Numbers
    3. Euler Witnesses
    4. Strong Witnesses
  24. Factorization Attacks
    1. Pollard's Rho Method [this section by Nov 13]
    2. Pollard's p-1 method
    3. Pocklington-Lehmer Criterion
    4. Strong Primes
    5. Primality Certificates
  25. Modern Factorization Attacks
    1. Gaussian Elimination
    2. Random Squares Factoring
    3. Dixon's Algorithm
    4. Non-Sieving Quadratic Sieve
    5. The Quadratic Sieve
    6. Other Improvements
  26. Finite Fields
    1. Making Finite Fields
    2. Examples of Field Extensions
    3. Addition mod P
    4. Multiplication mod P
    5. Multiplicative Inverses mod P
  27. Discrete Logs
    1. Baby-step Giant-step
    2. Pollard's Rho Method
    3. Logs in GF(32)
    4. Pohlig-Hellman Algorithm
    5. The Index Calculus
  28. Elliptic Curves
    1. Abstract Discrete Logarithms
    2. Discrete Log Ciphers
    3. Elliptic Curves
    4. Points at Infinity
    5. Projective Elliptic Curves
  29. More on Rings and Fields
    1. Ideals in Commutative Rings
    2. Ring Homomorphisms
    3. Quotient Rings
    4. Maximal Ideals and Fields
    5. Prime Ideals and Integral Domains
    6. More on Field Extensions
    7. Frobenius Automorphism
    8. Counting Irreducibles
    9. Counting Primitives
© July 2000, Paul Garrett ... [ home ] ... [ garrett@math.umn.edu ]
The University of Minnesota explicitly requires that I state that "The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota."