Wednesday, October 19th

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})^*\$.