RSA cryptosystem is mainly based on the multiplicative feature of Euler’s totient function. In this blog post, we embark on a gentle journey to unravel the elegant proof behind this remarkable property. By the end of our exploration, you’ll not only understand why Euler’s Totient Function is multiplicative, but also gain a deeper appreciation for the beauty and simplicity that underlie some of the most profound mathematical ideas. So, let’s dive into the world of number theory and discover the secrets of Euler’s Totient Function together.
Theory
Euler’s Totient Function, denoted as φ(n), calculates the number of positive integers less than or equal to n that are coprime (have no common factors other than 1) with n, providing a measure of the relative “primality” of n within the set of positive integers.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
It is also multiplicative function as
Φ(mn) = Φ(m)Φ(n) if and only if m and n are coprimes.
On the other hand, RSA enforces you to use two prime numbers. Two prime numbers will be coprime to each other. So, this rule will still be valid. Let’s represent this as
Φ(n) = Φ(pq) = Φ(p)Φ(q) where p and q are prime numbers.
We are going to prove this from the perspective of RSA in this post.
Totient function of a prime is its back number
It is obvious that Φ(p) = p – 1 if p is a prime number.
Total set
To find the totient of multiplication of two primes, we need to check numbers equal to the back number of the multiplication (n – 1) = (pq – 1).
T = {1, 2, 3, …, pq – 1}
Because, we know that even if this multiplication is prime, totient could be this value maximum whereas this multiplication cannot be prime because it is the multiplication of two primes.
In conclusion, there are pq – 1 numbers in the all set we are going to check.
The integers not relatively prime to n
We also know that numbers P={p, 2p, 3p, …, (q-1)p} are not relatively prime to n because n is equal to pq and each item in this set can be divisible by p it makes them not coprime with pq. Please notice that we increase the numbers until (q-1)p because qp is out of total set. So, there are, (q-1) different numbers that not relatively prime to n in set P.
Similarly, we also know that these numbers Q={q, 2q, 3q, …, (p-1)q} are not relatively prime to n. We increased the numbers until (p-1)q because pq is not a member of total set. So, there are (p-1) numbers that not relatively prime to n in set Q.
In conclusion, there are (p-1) + (q-1) numbers available in the total set that not relatively prime to n.
Can a number be in both set P and Q?
The answer is no because p and q are prime numbers according to RSA.
Let’s prove this. Suppose that same number is a member of P and Q sets (which is not possible). Name coefficients as x and y.
xp ?= yq
In this equation, we know p and q cannot be simplified. This equation can be satisfied only x = q and y = p. However, the maximum items are (q-1)p in set P and (p-1)q in set Q. So, a number cannot be a member of sets P and Q meanwhile.
Besides, these numbers do not have to be prime in the original definition of totient function. Being coprime is enough.
xm ?= yn
In this equation, we know m and n are coprimes. So, they cannot be simplified. This equation is just satisfied nm = mn where these are not member of sets P and Q. The largest numbers in those sets are (n-1)m and (m-1)n.
In conclusion, we can guarantee that no intersections available in those sets because of being coprime.
Result
Now, we are going to drop the numbers not relatively prime to n from the total set.
Φ(pq) = |T| – |P| – |Q|
Here |T| means the number of items in set T.
Φ(pq) = (pq – 1) – (p – 1) – (q – 1)
Φ(pq) = pq – 1 – p + 1 – q + 1
Φ(pq) = pq – (p + q) + 1
Φ(pq) = (p – 1)(q – 1)
On the other hand, totient function of p must be equal to p-1 because it is a prime.
Φ(p) = p – 1
Φ(q) = q -1
This can be represented as
Φ(pq) = (p – 1)(q – 1) = Φ(p)Φ(q)
So, we proven the multiplicative feature of Euler’s totient function!
Conclusion
In conclusion, we’ve embarked on a captivating mathematical journey to uncover the mystery behind Euler’s Totient Function’s multiplicative property. We’ve witnessed the elegance of number theory at work, revealing that when two positive integers are coprime, their totients multiply together. This result not only simplifies complex calculations but also underscores the profound interconnectedness of prime numbers and their powers. Euler’s Totient Function is a testament to the beauty and elegance that permeate the world of mathematics, reminding us that even the most abstract concepts can have tangible and practical implications in various fields, making the study of numbers a timeless and fascinating pursuit.
Like this blog? Support me on Patreon
