Compute Euler Phi Function of Large Integer | Matlab Solution

[paton51]

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?

 

[CRGreathouse]

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.

 

[CRGreathouse]

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:

(11:09)eulerphi(10^50+35)
time = 375 ms.
%10 = 52844036689487355925892416914616365612135546307584

 

[paton51]

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!

 

[CRGreathouse]

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):

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.

 

[Petter]

I'll reply because this thread is a top Google hit:

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))".