**Quiz (the Fourth) topics:**

- Euclidean algorithm (as always)
- Arithmetic in Z/nZ including inverses
- Arithmetic in explicit finite fields, including finding inverses (explicit means I tell you the integer and polynomial modulus)
- The size of finite fields
- Be able to create finite field examples by creating an integer and polynomial modulus; know the properties the integer and polynomial must have (i.e. integer is prime, polynomial is irreducible)
- Generalities on rings and fields (axioms)
- Know that there is exactly one finite field of size q^k
- Know the the invertible elements of a finite field have a multiplicative generator
- Be able to generalize the idea of discrete log, Diffie-Hellman and El Gamal to a finite field instead of Z/pZ
- Hash functions (3 basic properties, and example uses)
- El Gamal Digital Signature Algorithm (be able to implement it)
- Birthday attack for forging signatures
- Elliptic curves: what they are, how to add points (geometric algorithm), including special cases (P+P, point at infinity), how to find inverse of a point.
- be able to add points on an elliptic curve over the rationals, mod p or a finite field
- statement of Hasse’s theorem on number of points on an elliptic curve
- be able to find the number of points on an elliptic curve over finite field or mod p (don’t forget point at infinity)
- Elliptic Curve Discrete Logarithm problem — generalities (e.g. no subexponential known algorithms)
- be able to implement elliptic curve Diffie-Hellman Key Exchange, or explain how it works
- explain in theory how having a pairing gives you 3-party key exchange; no actual ability to implement required
- definition of a continued fraction, ability to compute using invert-and-take-integer-part.
- Birthday paradox: know how to compute the probability of a coincidence with n items (e.g. people) and N possibilities (e.g. days in the year)
- Know how to attack discrete log with birthday attack
- Projective space: definition, tell if elements are the same
- Projective space: whether functions or equations are well-defined and why
- Projective space: finding all solutions to a line or equation in projective space
- I won’t ask you to do elliptic curve computations in projective coordinates
- Basic terminology: SSL handshake, nonce, public key infrastructure, collision an collision-resistance, SHA-1, salt, dictionary attack on passwords, digital signature, irreducible polynomial
- Know, for all your algorithms, whether the runtime is exponential, sub-exponential or polynomial (no need for explicit formula memorization)
- No proofs on this one