1) Intro to El Gamal.

Let p = 23 and let base s=3.

a) Pick a number, a, between 2 and 21 to be your secret decoding number. Compute 3^a mod 23. Call this b.

b) Pick a secret message (for the time being, let it be a number, x) and another number, k both between 2 and 21.

Compute t = 3^k mod 23 and with your b from above compute y = b^k x mod 23.

c) Decode your secret number by computing (t^a)^{-1}y mod 23. You should have gotten x back; did you?

2) Compute the following phi(n) using our formula for phi.

phi(360)

phi(2222)

phi(2520)

phi(70000)