Problem 1 (Functions and matrices) [30 marks] Consider the set of or-dered pairs (x; y) where x are y are real numbers. Such a pair can be seen as a point in the plane equipped with Cartesian coordinates (x; y).
For each of the following functions F1; F2; F3; F4, determine a (2 2)-matrix A so that the point of coordinates (x y) is sent to the point (x0 y0 ) when we have
x0
= A
x
(1)
y0
y
where
A =
c
d
(2)
a
b
(a) F1(x; y) = (2y; 3x)
(b) F2
(x; y) = (0; 0)
(c) F3
(x; y) = (y; y)
(d) F4
(x; y) = (y + x; y
x)
Determine which of the above functions F1; F2; F3; F4 is injective? sur-jective? Justify your answer.
Problem 2 (Chinese Remaindering Theorem) [20 marks] Let m and n be two relatively prime integers. Let s; t 2 Z be such that s m + t n = 1. The Chinese Remaindering Theorem states that for every a; b 2 Z there exists c 2 Z such that
( x
2 Z
)
x
a
mod m
()
x
c mod m n(3)
8
x
b
mod n
where a convenient c is given by
c = a + (b a) s m = b + (a b)t n
(4)
Prove that the above c satis es both c a mod m and c b mod n.
Let x 2 Z. Prove that if x c mod m n holds then x a mod m and x b mod n both hold as well.
Let x 2 Z. Prove that if both x a mod m and x b mod n hold then so does x c mod m n.
1
Problem 3 (Solving congruences) [30 marks]
Find all integers x such that 0 x < 77 and 5x + 9 = 10 mod 77. Justify your answer.
Find all integers x such that 0 x < 77, x 2 mod 7 and x 3 mod 11. Justify your answer.
Find all integers x and y such that 0 x < 77, 0 y < 77, x + y = 33 mod 77 and x y = 10 mod 77. Justify your answer.
Problem 4 (RSA) [20 marks] Let us consider an RSA Public Key Crypto System. Alice selects 2 prime numbers: p = 5 and q = 11. Alice selects her public exponent e = 3 and sends it to Bob. Bob wants to send the message M = 4 to Alice.
Compute the product n = p q and (n)
Is this choice for of e valid here?
Compute d , the private exponent of Alice.
Encrypt the plain-text M using Alice public exponent. What is the resulting cipher-text C?
Verify that Alice can obtain M from C, using her private decryption exponent.
2
