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.