Reference no: EM132266173

Mathematics and Cryptography Assignment - Mathematics for Cryptography

Questions -

Q1. In each case find the gcd d = (m, n) of the given pair of integers m and n, and also find integers x and y such that d = mx + ny. Include all computations.

(a) 154, 126

(b) 484, -561

(c) -101, -103

Q2. Prove the following statements:

(a) Let a, b be given. Then (a, b) = 1 if and only if ax + by = 1 for some x, y, ∈ Z.

(b) Let a, c, b be given. Then (ab, c) = 1 if and only if (a, c) = 1 and (b, c) = 1.

(c) Let a, m, m' satisfy (m, m') = 1. Then (am', m) = 1 ⇔ (a, m) = 1.

(d) Let x, b, m be given. Then (x + bm, m) = (x, m).

(e) Let a, a', m, m' satisfy (m, m') = 1. Carefully prove

(a'm + am', mm') = 1 ⇔ (a, m) = 1 and (a', m') = 1.

Q3. Solve fully each of the following congruences. As part of your solution, present in full all computations, including those involving Euclid's algorithm.

(a) 117x ≡ 198 (mod 252)

(b) 117x ≡ 199 (mod 252)

(c) 55x ≡ 198 (mod 261)

(d) 55x ≡ 199 (mod 261)

Q4. Calculate the least residues 5¹, 5², 5³, 5⁴, 5⁵, 5⁶ (mod 7) and show that they form a complete set of least residues modulo 7 with the omission of 0. Repeat the calculations for 2¹, 2², 2³, 2⁴, 2⁵, 2⁶ (mod 7) and comment.

Q5. Suppose that A is a complete set of residues modulo n and b is an integer. Show that

A + b = {a + b : a ∈ A}

is also a complete set of residues modulo n.

Q6. A few computations

(a) Compute the least residue of 3^234567890 modulo 12.

(b) Using Euler's theorem, find the last three digits of 7¹³⁰⁰.

(c) Evaluate 2^5432675 modulo 13.

Q7. Here we consider the Euler function

(a) Compute Φ(10!).

(b) Show that if Φ(n) = n then n = 1.

(c) Show that Φ(n²) = nΦ(n).