By hand, using Gauss’ algorithm demonstrated in class, compute the inverse of 107 modulo 311. Here are notes from class today.

Compare your result to the result the computer provides using the Gauss Modular Inverse tool (which you will always be able to find in the website left-hand menu).

If you didn’t get it right, or your version took more steps, revisit it with another example: 40 modulo 311. Keep at it until you feel confident in your ability to do this correctly by hand.

Recall the exercises on DLP from the weekend. Please revisit these and compare to the solutions posted here. Make sure you are comfortable doing these exercises.

Revisit the algorithm you created for the last problem: finding the discrete logarithm of h modulo p, with respect to primitive root g. If you didn’t succeed at creating this algorithm, take a look at my solutions.

Now modify this algorithm so that it computes random powers of g until it happens to hit h. Have it output the total number of random guesses it needed to make before it hit h. You might want to use the Sage function randint(L,H) which returns a random integer between L and H inclusive.

Run a series of tests for different size prime p (the modulus), and various h. Note: you can find a primitive root mod p using the Sage command primitive_root(p). Make a conjecture as to the expected number of random guesses before finding h.

To hand in online: some evidence of your work above (e.g. sage code/data & guess and/or by-hand inverse computation examples).