Protoman wrote:

Hi! I'm trying to compute Euler's totient function for an extremely

simple RSA program I'm writing. How, exactly, is it calculated?

Thanks!

hello! I've studied the function a while ago, so I can give you a few

hints..

phi(p) = p-1 ; if p is a prime ;

phi(p^n) = p^n - p^(n-1) ; still if p is a prime.. I will not explain

how to get to this result, but let me know if you want the proof.

phi(a*b) = phi(a) * phi(b) whenever gcd(a,b) = 1

Thinking with the above points in mind, we can get to the conclusion

that the best (at last, the best way I can think of) is to simply

factor the given number. Here it is the code :

============================

static unsigned phi(unsigned long x) {

unsigned ret = 1,i,pow;

for (i = 2; x != 1; i++) {

pow = 1;

while (!(x%i)) {

x /= i;

pow *= i;

}

ret *= (pow - (pow/i));

}

return ret;

}

============================

Also, there is another formulae for computing phi if we know the prime

factorisation of p which is :

phi(x) = x*(1-1/f)*(1-1/f2)*...*(1-1/fn)

where f1,f2,fn are the factors of the given integer x. for example :

phi(60) = 60*(1-1/2)*(1-1/3)*(1-1/5) = 60x1/2*2/3*4/5 = 16

enjoy