Week 6 Problems

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

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

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

3. Let $P=353$ and $Q=359$. These are prime numbers. Let $N=PQ$ and $M=(P-1)(Q-1)$.

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

4. 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}\)