**Quiz the Third**

Note: Monday’s review on discrete log has solutions here.

**Material for the quiz:**

- Basic modular arithmetic
- Euclidean algorithm and inverses in modular arithmetic
- successive squaring for powers in modular arithmetic
- general ideas of feasibility (our discussion of powers of 2 and runtime)
- Pollard’s p-1 factorization (can explain and perform by hand)
- Sieve of Eratosthenes
- Sieving for smooth numbers
- Quadratic sieve factorization (can explain and perform by hand)
- Know what a continued fraction is and its principal properties
- Primitive roots
- Fact: a primitive root exists modulo any prime p (no proof given)
- The proposition of Section 3.7 (understand and can use the statement).
- Discrete Logarithm Problem and notation $L_g(h)$
- Understand formula for probability of coincidences in Birthday Paradox
- Baby-Step-Giant-Step algorithm (can explain and perform by hand)
- Index Calculus (can explain and perform by hand)
- know that Pohlig-Hellman exists and what sort of primes it works on
- Diffie-Hellman Key Exchange (can explain and perform by hand)
- ElGamal Public Key Cryptosystem (can explain and perform by hand)
- considerations for security and implementation of the above
- ElGamal Digital Signature Scheme (
**if** we get to it on Monday, Section 9.2)
- Proofs:
- novel proofs surrounding ideas of primitive roots and modular arithmetic
- proofs that DHE (Diffie-Hellman-Key-Exch) and ElGamal are correct, e.g. the decryption recovers the plaintext, or the shared secrets agree
- proof of Proposition of Section 3.7 or parts of that

- Terminology to know the basics of: factor base, smooth number, smoothness bound, exponential and sub-exponential run-times, birthday paradox, man-in-the-middle attack, notation $(\mathbb{Z}/p\mathbb{Z})^*$.

## Fall 2016 – Professor Katherine Stange