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.