Due Friday, September 25th

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.