To Know: This module has stretched a bit big, because there’s a lot of basic background (including runtimes, Big-Oh, lots about modular arithmetic) that we’ll build a lot of the course on. We still will talk about El Gamal and some methods for solving discrete log. I hope maybe to post the assessment early next week.

To Do: At the end of class today, I talked on the last slide about the “Birthday” attack on discrete log. The basic idea is to create two lists of elements and look for collisions (coincidences). Here is a scaffolded exercise: