- To know: I added a video about the Gauss modular inverse method to my YouTube channel.
- For the following problems, you can use a calculator and/or Sage for basic computations (reducing mod n, modular exponentiation, multiplication etc.). But otherwise work by hand showing your work.
- Solve the linear congruence 50x = 10 mod 75.
- Solve the linear congruence 13x = 14 mod 15.
- Solve the linear congruence 7x = 13 mod 14.
- The euler-phi function gives: phi(21733) = 21420. Use this fact to factor 21733. (Hint: revisit notes in class, I explained how to use a quadratic formula to do this).
- Suppose Eve has an RSA modulus n = 47053, and also knows the encryption and decryption exponents e = 3497 and d=2333. Use the method shown in class (adapated Miller-Rabin algorithm, also explained on page 168 of 2nd edition of text (in Section 6.1)), to factor n.
- In the problems above, show all the steps by hand and hand in on canvas. Useful functionality in Sage is basically just modular arithmetic functionality, but you might find the Miller-Rabin tool for determining how many powers of 2 are in something helpful.