# Wednesday, November 9th

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