xercise 6.1 Modular Arithmetic Find each of these values.
a) (−133 mod 23+261 mod 23) mod 23
b) (457 mod 23 · 182 mod 23) mod 23
Exercise 6.2 Fermat’s (Little) Theorem Show that 211,213 − 1 is not divisible by 11 .
Exercise 6.3 Euler’s Theorem
1. Compute φ(p2) where p is a prime.
2. Compute φ(pq) where both p and q are primes.
Exercise 6.4 Congruences
Find all solutions of the congruence 12x ≡ 27(mod18).
Exercise 6.5 Solving Congruences
What are the solutions of the linear congruence 101x ≡ 583(mod4620)?
Exercise 6.6 Fast Modular Exponentiation
22021 mod 2021
Exercise 6.7 Chinese Remainder Theorem Solve the following system of linear congruence
x ≡ 6 (mod11) x ≡ 13 (mod16) x ≡ 9 (mod21) x ≡ 19 (mod25)
Exercise 6.8 RSA
In an RSA procedure, the public key is chosen as (n,E) = (2077,97), i.e., the encryption function e is given by e(x) = x97 (mod2077)
(Note that 2077 = 31 × 67.)
Compute the private key D, where D = E−1(modφ(n)). Decrypt the message 279 , that is, find x if y = e(x) = 279(mod2077).
