MATH2088 Semester 2, 2022
1. (a) Compute the Euler totient function of 9828.
(b) Solve the following system of congruences{
x ≡ 49?1 (mod 73)
x ≡ 13 (mod 83).
(c) Compute gcd(10! , 2 · 3 · 5 · 7 · 11 · 13), where 10! means ten factorial.
(d) Compute 172216 (mod 41).
2. (a) A Vigenere cipher with the encryption key NOVEMBER has been used to pro-
duce the ciphertext JVDXQSESOWO.What was the plaintext?
The following table is provided for your convenience:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
(b) Amber and Bella have decided to share a secret key with help of the Diffie-
Hellman key exchange protocol. Amber sent Bella the triple (127, 6, 29) and
kept the value x = 5 secret. Then she received the number 13 from Bella.
Find the shared secret key s.
(c) A Rabin cryptosystem with the public key 77 is used to produce the en-
crypted message [71]. Find all possible plain messages.
3. (a) Show that for all a, b ∈ Z, a2 + 1 ≡ b2 + 1 (mod a+ b).
(b) Show the following result from lectures. Let numbers a, b ∈ Z and m, d ∈ Z+
satisfy ad ≡ b (mod md). Prove that d | b.
(c) For a k-bits long input, algorithms A, B and C take at most f(k), g(k) and
f(k)g(k) elementary bit operations respectively to complete. You are given
that f(k) = O(k3) and g(k) = O(k2 log2 k). Verify, if C is a polynomial time
algorithm or not. Justify your answer.
(d) Let n = pq be a product of two primes, e ∈ Z is coprime with ?(n) and
d ≡ e?1 (mod ?(n)). Given m ∈ Z, one computes m′ ≡ me (mod n) and
m′′ ≡ (m′)d (mod n). Show that m′′ ≡ m (mod n). You may use the RSA
theorem without proof.
MATH2088 Semester 2, 2022 page 2 of 2
4. (a) Find all x ∈ {0, 1, . . . , 88} such that
x61 ≡ 7 (mod 89).
(b) Are there primitive roots modulo 39? If yes then provide an example. If no
then provide a proof.
(c) Show that for all composite numbers n > 16, ?(n) < n? 4.
5. (a) You are given that p > 11 and that p, 2p+ 1 and 4p+ 3 are all safe primes.
Show that p ≡ 4 (mod 5).
(b) The baby-step/giant-step algorithm is used to find a solution of the congru-
ence
15x ≡ 93 (mod 139).
Some of the data produced by the algorithm is as follows:
15?12 ≡ 63 (mod 139),
k 0 1 2 3 4 5 6 7 8 9 10 11
15k (mod 139) 1 15 86 39 29 18 131 19
By restoring the missing data, find a solution x of the congruence.
(c) The Pollard’s Rho algorithm with parameters t0 = 1, tk+1 = t
2
k + 1 (mod n)
is used to factorise the number 94883. Some of the data produced by the
algorithm is as follows:
tk 2 5
t2k 5 677 25739 4468 6858
By restoring the missing data or otherwise find a non-trivial factor of 94883.
In this question you must not use the calculator’s factorisation features. All
the intermediate steps of the solution need to be provided.
This is the end of the examination paper