Compute Euler Phi Function of Large Integer | Matlab Solution

In summary: So, in summary, you can find the eulerphi function of a number by using prime factorization, then looping through the factors. You can also use the eulerphi function in MATLAB commands.
  • #1
paton51
8
0
How do i comput the euler phi function of a large interger?
i know that if p is prime then phi(p)=p-1 and I've found a formula for computing non primes but i don't know how to implement in something like Matlab.
Does anyone know how?
 
Physics news on Phys.org
  • #2
What, Matlab doesn't have that already?

phi is a multiplicative function: phi(ab) = phi(a) * phi(b) if gcd(a, b) = 1. So to find phi(n), first factor n and then find phi(p^k) for each prime p dividing n exactly k times. Have you seen the formula for that? Can you prove it?

As for implementing the formula, just loop through the factor vector.
 
Last edited:
  • #3
By the way, I assume this is for homework. If not, I strongly recommend Pari/GP rather than Matlab for number theory! The command in Pari/GP is eulerphi:

Code:
(11:09)eulerphi(10^50+35)
time = 375 ms.
%10 = 52844036689487355925892416914616365612135546307584
 
  • #4
Ok thanks i'll have a go at it. I don't have PARI/GP but i mite try and download it, i generally use MATLAB cus it relativly easy. Its not a homework question, a lecture mentioned it and I am just trying to understand it!
Thanks for your comments!
 
  • #5
No problem. I think that Pari is easier to use for these sorts of problems than Matlab, that's why I suggested it.

If you wanted to implement phi on your own in Pari (obviously it won't be quite as fast, but it'll help you understand):

Code:
myPhi(n)={
  local(f,t);
  f = factor(n);
  t = 1;
  for(i=1, #f[,1],
    t *= f[i, 1] - 1;
    t *= f[i, 1]^(f[i, 2] - 1);
  );
  t
}

The code loops through each prime component p^k and multiplies the running total t by p - 1 then by p^(k-1). For large n, most of the time is spent factoring (or proving primality) and so the code isn't actually that much worse in those cases.
 
  • #6
I'll reply because this thread is a top Google hit:
Code:
function phi = eulerphi(n)
	phi = n;
	for i = 1:length(n)
		p = unique( factor(n(i)) );
		phi(i) = phi(i) * prod(1 - 1./p);
	end
end
The for-loop makes the function work with vectors, which is useful for MATLAB commands like "stem(1:100,eulerphi(1:100))".
 

1. What is the Euler Phi function?

The Euler Phi function, also known as the totient function, is a mathematical function that counts the number of integers between 1 and a given number that are relatively prime to that number. It is denoted by φ(n) where n is the given integer.

2. How is the Euler Phi function computed?

The Euler Phi function can be computed using the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the prime factors of n. In other words, it is the product of n and the fractions (1-1/p) for each distinct prime factor of n.

3. How is the Euler Phi function useful?

The Euler Phi function has several applications, particularly in number theory and cryptography. It can be used to find the number of units (numbers with a multiplicative inverse) in a given modulus, to determine the order of an element in a group, and to check for primality of a number.

4. How can the Euler Phi function be computed for large integers?

For large integers, it is not possible to compute the Euler Phi function using the traditional formula as it would require factoring the number into its prime factors. However, there are efficient algorithms, such as the Sieve of Eratosthenes, that can be used to compute the Euler Phi function for large integers.

5. How can the Euler Phi function be computed using Matlab?

Matlab has a built-in function called eulerphi that can be used to compute the Euler Phi function for a given integer. It takes the integer as an input and returns the value of φ(n). This function can also be used for large integers as Matlab has efficient algorithms to handle large numbers.

Similar threads

Replies
13
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
6
Views
2K
Replies
1
Views
759
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
951
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
3
Views
6K
  • Calculus and Beyond Homework Help
Replies
8
Views
558
Replies
10
Views
578
  • MATLAB, Maple, Mathematica, LaTeX
Replies
8
Views
1K
Back
Top