Write down the prime factors of the numbers 21, 36, 91 and 126.

1) Write down the prime factors of the numbers 21, 36, 91 and 126.
2) What is the greatest common divisor of 36 and 126?
3) Show the steps taken by Euclid s algorithm in computing the greatest common divisor of 210 and 54.
4) Show the steps taking by Euclid s algorithm in computing the greatest common divisor of 105 and 27. What do you notice about how this run of Euclid s algorithm compares to that from part 2(a)?
5) Write out the multiplication table for the integers 1, 2, 3, 4, 5 and 6 modulo 7.
6) Compute the powers of 2 modulo 7; that is, the values of 21, 22, 23, etc. The sequence will eventually repeat itself; you do not need to keep writing it out at this stage!
7) Compute the powers of 5 modulo 7; that is, the values of 51, 52, 53, etc.
8) What are the orders of 2 mod7 and 5mod 7?
9) Alice and Bob want to agree on a shared secret key using the Diffie-Hellman protocol. They decide to use 11 as the modulus and 2 as the generator. Alice thinks of the secret number 9 and Bob thinks of 4.
(a) What messages do Alice and Bob send one another?
(b) What calculations do they perform with those messages?
(c) What is the value of the shared secret key they arrive at?
10) What is XXXXXXXXXXX mod 11? (hint: use Fermat s Little Theorem and show all of your working)