Description
Ex. 1 — Euler’s totient
Let ϕ be Euler’s totient function.
1. Prove that for any prime p, ϕ(p
k
) = p
k−1
(p − 1).
2. Prove that for any two coprime integers m and n, ϕ(mn) = ϕ(m)ϕ(n).
3. Using the previous results prove that for any integer n > 1, we have
ϕ(n) = n
Y
p|n
1 −
1
p
4. What are the three last digits of 7803?
Ex. 2 — AES
Supposed a round 0 AES key is composed of 128 1.
1. What is the key used for round 1?
2. Observe K(5) and express it in term of K(4).
3. Prove that K(10) = K(8) and K(11) = K(9).
Note: x denotes the complement of x, that is 0s become 1s and 1s become 0s.
Ex. 3 — Simple questions
1. A plaintext is split into blocks and then encrypted. If one block is corrupted during transmission
show that the number of plaintext decrypted incorrectly is one for the ECB mode and two for
CBC.
2. Show that using CBC mode with an IV incremented by 1 each time, instead of being random,
results in schemes that are not CPA secure.
3. Prove that 2 is a generator of U(Z/29Z).
4. Determine
1801
8191
.
5. Let a, b, c be three integers and p be an odd prime not dividing a. Prove that the number of
solutions mod p to the equation ax2 + bx + c = 0 is 1 +
b
2−4ac
p
.
6. Let p and q be two primes such that p > q > 2 and q−1 divides p−1. Show that if gcd(n, pq) = 1,
then n
p−1 ≡ 1 mod pq.
7. Let p be an odd prime. Prove that
−3
p
= 1 if and only if p ≡ 1 mod 3.
8. Let p be a prime. Prove that if
a
p
= 1, then a is not a generator of F
∗
p
.
Ex. 4 — Prime vs. irreducible
In a commutative ring R, a non-zero, non-invertible element p is said to be prime if for any x, y ∈ R,
p | (x · y) implies p | x or p | y. (∗)
The goal of this exercise is to prove that this definition generalizes the definition of primality for integers,
i.e., p ∈ Z is prime if
p > 1 and a | p implies a = 1 or a = p. (∗∗)
1. Prove that in an integral domain, i.e. a commutative ring in which the product of two nonzero
elements is nonzero, any prime element (in the sense of (∗)) is irreducible.
2. Prove that in Z any irreducible integer is prime in the classical sense (∗∗).
3. Prove that for p ∈ Z, (∗∗) implies (∗).
4. Conclude that (∗) and (∗∗) are equivalent for integers.
Ex. 5 — Primitive root mod 65537
1. Show that
3
65537
= −1.
2. Show that 332768 6≡ 1 mod 65537.
3. Conclude that 3 is a primitive root mod 65537.
