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