Untitled
CM30173: Example sheet 6
6th March
All questions relate to mathematical background sections and RSA.
1. Which elements of Zn have multiplicative inverses? How many elements of Z143 have
multiplicative inverses? When is Zn a field?
2. Calculate using only a calculator the following:
gcd(80446, 22382)
gcd(41275, 5577)
3. In lecture 11 when describing the basic Euclidean algorithm I said that it could be shown
that gcd(a, b) = gcd(r0, r1) = . . . = gcd(rm−1, rm) = rm. Prove that this is the case.
4. Use the extended Euclidean algorithm to compute the following multiplicative inverses:
13−1 (mod 103)
8−1 (mod 105)
5. With a, b, ri, ti, si defined as in the extended Euclidean algorithm (lecture 11) prove that
ri = sia + tib for all 0 ≤ i ≤ m
6. Solve the following system of congruences:
x ≡ 3 (mod 15)
x ≡ 9 (mod 16)
x ≡ 16 (mod 17)
7. Let gcd(m1, m2) = 1 explain why the pair of congruences
x ≡ a (mod m1)
x ≡ a (mod m2)
has unique solution x ≡ a (mod m1m2).
8. Let (13, 11, 7) be Bob’s private RSA key, find his public key. Use his public key to encrypt
x = 3 and ensure that you can decrypt it again.