RSA

Given primes p and q

1. Confirm p and q are prime using Fermat's little theorem prime test.
   1. Show the steps of how this is done using fast modular exponentiation.
2. Let n = p*q and totient = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1).
   1. Show the steps of computing gcd(p-1, q-1) using the Euclidean algorithm.
3. Find the smallest e > 1 such that gcd(e, totient) = 1.
4. Let d be the inverse of e mod totient.
   1. Show the steps of computing d using the extended Euclidean algorithm.
5. Your public key: n, e
6. Your private key: n, d

Take a given ciphertext c and computer c**d mod n to decrypt the message.