Euler's phi Algorithm
INTRODUCTION
Euler's totient function (also called phi-function or totient function) takes a
single positive integer n as input and outputs the number of integers present
between 1 and n that are co-prime to n.
Note:
• 2 positive integers a and b are said to be co-prime if their greatest common
factor/divisor is equal to 1, that is,
gcd(a,b)=1
• 1 is considered co-prime to all numbers.
Example: Find Փ(5)
Solution
Here n=5
Numbers less
Euler’s Phi than 5 are 1,2,3 and 4
Algorithm
GCD Relatively Prime?
GCD(1,5)=1
GCD(2,5)=1
GCD(3,5)=1
GCD(4,5)=1
There are 4 numbers less than 5 that are co-prime to it
Therefore Փ(5)=4
Example: Find Փ(11)
Solution
Here n=11
Numbers less than 11 are 1,2,3,4,5,6,7,8,9 and 10
GCD Relatively GCD Relatively
Euler’s PhiPrime?
Algorithm Prime?
GCD(1,11)=1 GCD(6,11)=1
GCD(2,11)=1 GCD(7,11)=1
GCD(3,11)=1 GCD(8,11)=1
GCD(9,11)=1
GCD(4,11)=1
GCD(10,11)=1
GCD(5,11)=1
there are 10 numbers less than 11 that are co-prime to it
Therefore Փ(11)=10
Example: Find Փ(8)
Solution
Here n=8
Numbers less than 8 are 1,2,3,4,5,6 and 7
GCD Relatively GCD Relatively
Euler’s PhiPrime?
Algorithm Prime?
GCD(1,8)=1 GCD(5,8)=1
GCD(6,8)=2
GCD(2,8)=2
GCD(3,8)=1 GCD(7,8)=1
GCD(4,8)=4
There are 4 numbers less than 8 that are co-prime to it
Therefore Փ(8)=4
Properties
Criteria of 'n' Formula
'n' is prime. Φ(n) = (n-1)
n=pxq
Φ(n) 'p' and 'q' are primes. Φ(n) = (p-1) × (q-1)
n = a x b.
Either 'a' or 'b’ is composite.
Both 'a' and 'b' are composite.
Property 1
Criteria of 'n' Formula
Φ(n)
'n' is prime. Φ(n) = (n-1)
Proof: Find Φ(7)
Here n=7 - ‘n’ is a prime number
Φ(n) = (n-1)
Φ(7) = (7-1)
Φ(7) = 6
there are 6 numbers less than 7 that are co-prime to it
Therefore Փ(7)=6
Property 2
Criteria of 'n' Formula
Φ(n) n=pxq Φ(n) = (p-1) × (q-1)
'p' and 'q' are primes.
Proof : Find Φ(35)
Here n=35 - ‘n’ is a product of two prime numbers 5 and 7
Let us assign p=5 and q=7.
Φ(n)=(p-1) × (q-1)
Φ(35)=(5-1) × (7-1)
=4x6
= 24
So, there are 24 numbers that are lesser than 35 and relatively prime to 35.
Therefore Փ(35)=24
Property 3
Criteria of 'n' Formula
Φ(n) n = a x b.
Either 'a' or 'b’ is composite.
Both 'a' and 'b' are composite.
The idea is to count all prime factors and their multiples and subtract this count
from n to get the totient function value
(Prime factors and multiples of prime factors won’t have GCD as 1)
Algorithm
1) Initialize result as n
2) Consider every number 'p' (where 'p' varies from 2 to Φn).
If p divides n, then do following
a) Subtract all multiples of p from 1 to n [all multiples of p will have gcd
more than 1 (at least p) with n]
b) Update n by repeatedly dividing it by p.
3) If the reduced n is more than 1, then remove all multiples of n from result.
class Euler {
int EulersTotient (int N)
{
// Setting initial number of totatives to N
int ans = N;
for (int i=2; i*i <= N; i++)
{
if (N % i == 0)
{
ans = ans - ans/i;
}
while (N % i == 0)
N = N/i;
}
if (N > 1)
ans = ans - ans/N;
return ans;
}
public static void main (String args[])
{
Euler obj = new Euler();
System.out.println("Φ(15) = " + obj.EulersTotient(15));
System.out.println("Φ(12) = " + obj.EulersTotient(12));
System.out.println("Φ(17) = " + obj.EulersTotient(17));
System.out.println("Φ(9) = " + obj.EulersTotient(9));
System.out.println("Φ(98) = " + obj.EulersTotient(98));
System.out.println("Φ(100) = " + obj.EulersTotient(100));
}
}
Interview questions
What is Euler's Phi algorithm?
Answer: Euler's Phi algorithm is a mathematical algorithm used to
calculate the totient function of a given number. The totient function
(φ(n)) is the number of positive integers less than or equal to n that
are relatively prime to n.
Interview questions
What is the time complexity of Euler's Phi algorithm?
Answer: The time complexity of Euler's Phi algorithm is
O(sqrt(n)), where n is the input number.
Interview questions
What are some applications of Euler's Phi algorithm?
Answer: Euler's Phi algorithm has several applications in number
theory and cryptography. It is used in RSA encryption and
decryption, as well as in the generation of keys for public key
cryptography. It is also used in determining the order of an element
in a group, and in solving the discrete logarithm problem.
Interview questions
Can Euler's Phi algorithm be used for large numbers?
Answer: Euler's Phi algorithm can be used for large numbers, but it
may become computationally expensive due to the prime factorization
step. In some cases, it may be necessary to use more advanced
algorithms for calculating the totient function of very large numbers.
Interview questions
What is the significance of Euler's Phi function?
Answer: Euler's Phi function is significant in number theory and
cryptography as it is used in many mathematical proofs and
algorithms. It has applications in determining the relative primality of
two numbers, generating RSA keys, and solving the discrete
logarithm problem, among other things.
Interview questions
How does Euler's Phi algorithm differ from the Sieve of Eratosthenes?
Answer: Euler's Phi algorithm and the Sieve of Eratosthenes are two
different algorithms used in number theory. The Sieve of Eratosthenes is
used to find all the prime numbers up to a given limit, while Euler's Phi
algorithm is used to calculate the totient function of a given number. The
two algorithms have different purposes and use different methods to
accomplish their respective tasks.
THANK YOU
