MATH3301 NUMBER THEORY AND CRYPTOGRAPHY: ASSIGNMENT 3
DUE: FRIDAY, 29/09/2023, 6:00 PM
In all questions below, you must justify your answers. All computations should be shown in the solution except
easy computations, which are division or multiplication of two numbers of length 4 or less (e.g. if you multiply three
4-digit numbers modulo m, provide the product of the first two modulo m, and then multiply this product by the
third number modulo m). For question 4(b), you can compute exponents modulo n without explanations.
(1) Is 2821 prime? (20 marks) Without finding a factorisation of 2821:
(a) show that it is a base 3 pseudoprime, and
(b) use Miller’s test in base 3 to show that it is composite.
You should use the fast modular exponentiation from lectures in both parts of the question.
(2) Cryptanalysis of an affine shift cipher (20 marks) Suppose you knew that a great 20th century British com-
puter scientist used an affine shift cipher to encrypt the following message which you have intercepted:
KEQRY IURY TERHYNROKLGTHBGY TQGRHGTBGTG.
You are aware that the three most frequently occurring letters in the message are E (17%), N (14%) and R
(14%), where the percentages denote average letter frequencies. Use this information to guess how two letters
in this message should be decrypted then use your guess to reconstruct the encryption key for this crypto-
system and decrypt the message. To save you some time, there are 37 letters in this cipher text and the most
frequently occurring are G (6 times), R (5 times), and T (5 times).
(3) Iterating affine shift ciphers (20 marks) Let E(a,b) denote an affine cipher encryption.
(a) Prove that there exists a positive integer k such that
Ek(a,b) = Id,
for all keys (a, b), where Ek denotes the kth composition of the map E. In other words, for every plaintext
m, if we encrypt it k times, we will get m again:
E(a,b)(E(a,b)(E(a,b)(. . . (E(a,b)︸ ︷︷ ︸
k times
(m))))) = m.
Provide the value for k which does not depend on a or b; namely, k should be just a number.
(b) Find the minimal value of k, such that
Ek(a,b) = Id,
for all keys (a, b) with a ̸≡ 1 mod 26.
(c) Find the minimal value of k, such that
Ek(a,b) = Id,
for all keys (a, b).
(4) RSA (20 marks). You are using the RSA system with a public key (n, e) = (3127, 255).
(a) Compute your private key.
(b) Decrypt the message 0381 0345 1213 0534 obtained from a 7-letter word.
1
(5) Orders (20 marks) Find ord27(a) for all 1 ≤ a ≤ 27 coprime to 27.
Hint. To simplify the computations, first find a primitive root and use it to find the orders of all other
elements.