Due Friday:
- 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:
- Let p = 113, g=3 (a primitive root), and h = 34.
- Using the tools at the Birthday/BSGS Demo:
-
- make a list of some random powers g^x (try N=11 of them to start)
- make a list of some random h*g^x (again, try N=11 of them to start)
-
- look for a collision between the two lists (if none found, increase N and keep trying)
- using the collision you find, and the ideas in the notes at the end of the last class, determine the discrete log of h with respect to g.
- Hand in your computation on canvas.