Assignment #3 Cartesian coordinates

Assignment #3

Submission: on the OWL web site of the course
Problem 1 (Functions and matrices) [30 marks] Consider the set of ordered 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).
1. 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
(x
0 y
0
) when we have
?
x
0
y
0
?
= A
?
x
y
?
(1)
where
A =
?
a b
c d ?
(2)
(a) F1(x, y) = (2y, 3x)
1
(b) F2(x, y) = (0, 0)
(c) F3(x, y) = (y, y)
(d) F4(x, y) = (y + x, y − x)
2. 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 ∈ Z be such that s m + t n = 1.
The Chinese Remaindering Theorem states that for every a, b ∈ Z there
exists c ∈ Z such that
(∀x ∈ Z)
?
x ≡ a mod m
x ≡ b mod n
⇐⇒ x ≡ c mod m n (3)
where a convenient c is given by
c = a + (b − a) s m = b + (a − b)t n (4)
1. Prove that the above c satisfies both c ≡ a mod m and c ≡ b mod n.
2. Let x ∈ Z. Prove that if x ≡ c mod m n holds then x ≡ a mod m
and x ≡ b mod n both hold as well.
3. Let x ∈ Z. Prove that if both x ≡ a mod m and x ≡ b mod n hold
then so does x ≡ c mod m n.
Problem 3 (Solving congruences) [30 marks]
1. Find all integers x such that 0 ≤ x < 77 and 5x + 9 = 10 mod 77.
Justify your answer.
2. Find all integers x such that 0 ≤ x < 77, x ≡ 2 mod 7 and x ≡ 3
mod 11. Justify your answer.
3. 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.
1. Compute the product n = p q and Φ(n)
2. Is this choice for of e valid here?
3. Compute d , the private exponent of Alice.
4. Encrypt the plain-text M using Alice public exponent. What is the
resulting cipher-text C?
5. Verify that Alice can obtain M from C, using her private decryption
exponent.
2