To complete the theory required to understand RSA, the final mathematics we are going to look at is Euler’s Totient Function and Euler’s Theorem.
Euler’s Totient Function
Euler’s totient function, also known as the phi function, counts the number of positive integers less than n that are coprime to n. Mathematically, ϕ(n) is the number of m ∈ N such that 1 ≤ m < n and gcd(m, n) = 1. We can also define ϕ(n) = |Un| where Un denotes the set of units in Zn. To understand units, basic group theory knowledge may be required but we won’t be going into detail here.
Example:
1. Find ϕ(6).
ϕ(6) is made up of units {[0]6, [1]6, [2]6, [3]6, [4]6, [5]6}. First, we cross off elements that are not relatively prime.
ϕ(6) = |U6|
= {[1]6, [5]6}
= 2
2. Find ϕ(15)
Eliminate the multiples of 3 or 5, {3,5,6,9,10,12}. The remaining numbers are {1,2,4,7,8,11,13,14}, so ϕ(15) = 8.
Lemma:
If n = pe where p is prime, then
ϕ(n) = pe - pe-1
= pe-1(p – 1)
= n(1 – 1/p)
Proof:
ϕ(pe) is the numbers of integers in {1,…,pe} which are coprime to pe, i.e. not divisible by p. This set has pe members, of which pe/p = pe-1 are multiples of p, so ϕ(pe/) = pe - pe-1
= pe-1(p – 1). ■
Corollary:
If n has prime-power factorisation n = p1e1…pkek, where pi and ei > 0, then
ϕ(n) = n(1 – 1/ p1)(1 – 1/ p2)…(1 – 1/ pk)
Example:
Find ϕ(60).
The primes dividing 60 are 2, 3 and 5, so
ϕ(60) = 60(1 – 1/2)(1 – 1/3)(1 – 1/5)
= 60 * 1/2 * 2/3 * 4/5
= 16.
Theorem:
If a and b are coprime, gcd(a, b) = 1, then ϕ(ab) = ϕ(a)ϕ(b).
Example:
1. Find ϕ(12).
12 can be split into the integers a = 3 and b = 2, which are coprime with ϕ(3) = ϕ(4) = 2. Hence ϕ(12) = 2*2 = 4.
2. Find ϕ(15).
ϕ(p) can be written as p – 1 so;
ϕ(15) = ϕ(3)ϕ(5)
= (3 – 1)(5 – 1)
= 2 * 4
= 8
Euler’s Theorem
In 1760, Euler proved the following generalisation of Fermat’s Little Theorem.
Theorem:
If gcd(a, n) = 1, then aϕ(n) ≡ 1 mod (n).
Example:
Find ϕ(14), and verify that aϕ(14) ≡ 1 mod (n) for each a coprime to 14.
ϕ(14) = ϕ(2)ϕ(7)
= (2 – 1)(7 – 1)
= 1 * 6
= 6
U14 = {[±1], [±3], [±5]}
(±1)6 = 1 (mod 14)
(±3)6 = 729 ≡ 1 (mod 14)
(±3)6 = 15625 ≡ 1 (mod 14)
RSA relies heavily of the above theorems so make sure you understand them before moving on to computing RSA algorithms.
Written by JaneW