Department of Mathematics
MATHS 328 Assignment 2. Questions Due: 15 April 2024
1. (20 points) Eve eavesdrops on the correspondence of Ark, Pip and Tom who use Hill’s cryptosystem
to communicate. She discovered that they split messages into segments which are three letters long
and that the names ARK, PIP and TOM are encoded as GCB, APM and BWZ, respectively.
Find the matrix K which is used as the key.
2. (20 points) Prove that for any fixed positive integer d(
n
d
)
= Θ(nd)
i.e., the binomial coefficient grows polynomially in n.
3. (20=10+10 points) Let us call a number N almost prime if does not have prime divisors smaller
than (log2N)
2.
(a) Prove that there exist almost prime numbers that are composite.
(b) Using GAP find an almost prime number that is composite.
4. (20 points) Alice and Bob have the following RSA parameters:
nA = 116843187579509698439177769751386474940457877351734068668377, eA = 1234567,
nB = 41989230468376560622264958706569326838563915099140031193663, eB = 7654321.
Bob creates a message to Alice splitting it into two parts m1 and m2, then signs the last bit applying
his decryption key to m2 obtaining m3. Then he encrypts the whole message with Alice’s public
key obtaining the cryptotext c = [c[1], c[2], c[3]] where
c[1] = 113438632352422763265675742513046812673537179044234633006538,
c[2] = 45013089611237457780987479205118742551558572798511252012986,
c[3] = 111491725228799790475033209306493492319899494161842598114763
Demonstrate how Eve will decrypt this message, when intercepted, and check that it has come
indeed from Bob.
5. (20 points) Prove that any witness b of compositeness of n for the test based on Little Fermat
theorem (Test 3 in lectures) will be also a witness of compositeness of n for the Rabin-Miller test
(Test 4 in lectures).
6. (5 bonus points) Let k be a positive integer such that the three numbers 6k + 1, 12k + 1, 18k + 1
are all prime numbers. Prove that their product n = (6k + 1)(12k + 1)(18k + 1) is a Carmichael
number. Use GAP to find first five Carmichael numbers of this kind.
MATHS 328 Assignment 2. Questions Page 1 of 1