Due Friday October 9th:

Due Friday:

  • 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.