Euler’s Totient Function – Counting Primes

Euler came up with this function more than 200 years back. At that time this function drew less attention, indeed it had no much value as there is no direct application other than in number theory. However, today this function plays a major role in cyber security applications.

Euler’s Totient Function, also known as Phi Function, Prime Counting Function or \displaystyle \varphi(n) is used to count number of co-primes prior to a given integer. In other words, the function outputs number of co-primes which are less than the given number.

Co-primes are integers which does not share any common factors. For an example even though 8 is not a prime, it is a co-prime of 15. Because 8 = 2*2*2 and 15 = 2*5, therefore it can be seen that 8 or 15 does not share a common factor.

If a given integer is a prime, obviously all the integers less than the given number are co-primes to the given prime. Therefore, it is easy to calculate \displaystyle \varphi(n) if n is a prime. When n is a prime; in \varphi(n) = \displaystyle (n - 1)

When n is not a prime, \displaystyle \varphi(n) can be calculated as follow:

First, the number should be broken into prime factors, then after it is a matter of applying the following equation:

n = \displaystyle p_1 * p_2 * ....... p_m (prime factors of n)

\varphi(n) = \displaystyle n \prod_{i=1}^{m} ( 1 - \frac{1}{p_i} )

Multiplicative Property

This is another interesting property of \displaystyle \varphi(n) which can be used to compute \displaystyle \varphi(n).

When, p and q are prime numbers:

\varphi(n) = \displaystyle \varphi(p) * \varphi(q)

as a fact, if p and q are prime numbers then, \varphi(p) = \displaystyle (p - 1) * (q - 1)

Example

Calculating \displaystyle \varphi(24) :

24 = \displaystyle 2^3 * 3

Using the above equation:

\varphi(n) = \displaystyle n \prod_{i=1}^{m} ( 1 - \frac{1}{p_i} )

n = 24, m = 2 and primes are 2, 3:

\varphi(24) = \displaystyle 24 * ( 1 - \frac{1}{2} ) * ( 1 - \frac{1}{3} )

\varphi(24) = \displaystyle 24 * ( \frac{1}{2} ) * ( \frac{2}{3} )

\varphi(24) = \displaystyle 24 * ( \frac{1}{3} )

\varphi(24) = \displaystyle 8

Will check if the answer is correct, using the besic definition:

Following are all the integers less than 24, starting from 1

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23

Remove co-prime of 24:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23

Remaining number count is 8, therefore both answers match.

Python Implementation

It is possible to use the above equation to calculate \varphi(n) \displaystyle in Python. However, it is easier to use the definition of prime counting rather than using the equation.

The algorithm would be as follow:

  1. \varphi(n) \displaystyle needs to be calculated.
  2. Start from k = 2, counter is 0.
  3. Check if the selected integer (k) is a co-prime to n.
  4. If it is a co-prime increase the counter.

To check if k is a co-prime to n, GCD operation can be used.

def calculate_phi(n):
    phi_n = 1
    count = 0
    i = 2
    while (i<n):
        r = gcd_euc(n, i)
        i = i + 1
        if(r==1):
            phi_n = phi_n + 1
    return phi_n

Summary

Above mentioned methods can be used to calculate \displaystyle \varphi(n) of a given integer.  Results of the phi function is often applied in cryptography.

Advertisements

Please add your valuable idea below, will make a discussion, thanks !

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s