Week 6 Problems
Note: you will probably need a computer to solve these problems. Wolfram alpha can do what you need.

Find $\phi(n)$ for $n=51,60,100$.

Use repeated squaring to check that \(2^{100}\equiv 1\pmod{101}.\)

Let $P=353$ and $Q=359$. These are prime numbers. Let $N=PQ$ and $M=(P1)(Q1)$.
 Solve the equation \(3x\equiv 1\pmod{M}\) Using Euclid’s algorithm.
 Assume $3$ is the public key and $x$ is the secret key for an RSA system. Encrypt the message “100” using the public key. What is the value of this message?
 Verify that you can decrypt the message using the secret key to obtain “100”.

The number $F_5=2^{32}+1=4,294,967,297$ is called the fifth Fermat number. Prove that it is composite by computing \(3^{F_{5}1} mod F_{5}\)