We have been commonly using the Euler’s generalized version of Fermat’s little theorem in RSA encryption algorithm. In this post, we will prove the Fermat-Euler Theorem with number theory.
Vlog
You can continue to read this tutorial or watch the following video. They both cover the proof of Fermat-Euler theorem.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Alternatively, Fermat’s Little Theorem can be proven by induction.
Fermat’s little theorem
Let’s remember what was the Fermat’s little theorem.
ap – a = 0 mod p
while p is a prime number and a and p pair is coprime. We have already proven this version of Fermat’s little theorem with necklace and induction methods in this blog. We can re-organize this equation.
Firstly, we will move the minus a term from left hand side to right hand side.
ap = a mod p
Thereafter, we can simplify the both sides with dividing to a.
ap-1 = 1 mod p
This form of Fermat’s little theorem looks more like to Euler’s theorem.
Euler’s theorem
Modulus must be a prime number in the definition of Fermat. Euler’s one comes with some modifications and being a prime number is not a must for the modulus. That is why, n variable is commonly used to represent modules in Euler’s theorem instead of p.
aφ(n) = 1 mod n
Besides, totient function φ(n) is used in the power in contrast to Fermat’s one. Totient function counts the positive integer numbers coprime to n. We already know that it would be n-1 while n is a prime number.
Totient function
This theorem is also called as Euler’s Totient Theorem.
As mentioned, totient function counts positive integers that coprime to n. For example, numbers that coprime to 9 are {1, 2, 4, 5, 7, 8}. So, φ(9) = 6.
This can be found with python programming language with the totient function. Notice that time complexity of that function is O(n) in the big O notation. This becomes problematic for very large values.
def gcd(p,q):
while q != 0:
p, q = q, p%q
return p
def totient(n):
coprimes = 0
for i in range(1, n): # [1, n)
if gcd(n, i) == 1:
coprimes += 1
return coprimes
But totient function comes with some advantages. It is a multiplicative function. If you can represent the value n as multiplication of two integers that coprime to each other, then you can multiply the totient of the multipliers.
φ(pxq) = φ(p)xφ(q)
In the case p and q are both prime numbers, then they will be coprime to each other. Precondition of this property is satisfied. Also, totient value of a prime number p must be p-1.
φ(pxq) = φ(p)xφ(q) = (p-1)(q-1) if p and q are prime number
That is why, module n is the multiplication of two primes in RSA cryptosystem. In that way, you can find the totient n with O(1) instead of O(n).
Proof
Euler’s theorem states
aφ(n) = 1 mod n
while a is any integer not divisible by n. In other words, a and n are coprime.
Suppose that numbers coprime to n are stored in set S.
S = {x1, x2, …, xφ}
So, the length of set S is φ(n).
Let’s create a new set by multiplying all items of set S with a.
T = {ax1, ax2, …, axφ}
We already know that all x items in the set S must be less than n.
0 <= xi < n
On the other hand, the multiplication of a and x values in the set T would be greater than n. Finding the mod n values of all items in the set T makes all items less than n as well. That is why, let’s create a new set with finding the mod n of each item in set T.
K = {ax1 mod n, ax2 mod n, …, axφ mod n}
Besides, we know that a and xi values are both coprime to n. So, its multiplications will be coprime to n. Herein, numbers that coprime to n are already stored in the set S! So, items of set K must have 1-to-1 relationship with items of set S.
We can express this in the programming literature as: ax1 mod n in [x1, x2, …, xφ] && ax1 mod n in [x1, x2, …, xφ] && .. && axφ mod n in [x1, x2, …, xφ]
We exactly do not know the relationships but e.g. if (ax1 mod n) is equal to x2, then no other items in the set K should be connected to x2. Let’s represent the results which i, j, k variables.
xi = ax1 mod n
xj = ax2 mod n
…
xk = axφ mod n
We know that xi, xj, … xk items must be a member of set S. And all items in the set S must be covered with a value from set K. So, if I multiply all item in the left hand side, it would be the multiplication of all items in the set S.
Let’s multiply all equations and create just one equation. I need to multiply them values in the left hand side to each other, and right hand side to each other.
x1 x2 … xφ = ax1 mod n ax2 mod n … axφ mod n
We know that there are φ(n) items in the set S, T and K. So, there are φ(n) different a items available in the right hand side.
x1 x2 … xφ = aφ(n) (x1 x2 … xφ) mod n
We can simplify the x terms in the both side of the equation.
1 = aφ(n) mod n
So, we can prove the Euler’s theorem! This is the backbone of RSA algorithm as is. The algorithm expects you to pick two large primes p and q, then find n=pxq and φ(n)=φ(pxq)=φ(p)xφ(q)=(p-1)(q-1).
Like this blog? Support me on Patreon
