Computing Euler's totient function

[Protoman]

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!

 

[Pascal Bourguignon]

Hi! I'm trying to compute Euler's totient function for an extremely
simple RSA program I'm writing. How, exactly, is it calculated?

Do you know Google? It's this fine web site: http://www.google.com/
You type in keywords, and it gives you a list of web pages with these keywords.
The nice thing, is that most often you can find the answer to your
question on these we pages, just because the keywords of your
questions appear in the answers. Kind of magical! Try it!


--
__Pascal Bourguignon__ http://www.informatimago.com/

HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.

 

[wooks]

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!

You can look up this information in any number theory textbook or you
can search on the web. It's a maths question not a programming question.

 

[Peter Luschny]

Do you know Google? It's this fine web site: http://www.google.com/

Being a coding question it is even better to use:
http://www.google.com/codesearch Or all in one line:
http://www.google.com/codesearch?q=Euler's+totient&hl=en&btnG=Code

 

[stdazi]

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

 

[Nikolaos D. Bougalis]

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!

[solution to the homework problem the OP was having]

Congratulations. Instead of helping the OP, by giving him a helpful pointer
that would have required him to do his own homework and to learn something in
the process, you do it for him and teach him how to copy-paste. Perhaps when
he graduates and can't code anything, he can come work where you work, and
you'll still be so kind as to do his work for him, while he sits back and
collects a paycheck.

Bah!

-n

 

[azi.stdout]

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!

[solution to the homework problem the OP was having]

Congratulations. Instead of helping the OP, by giving him a helpful pointer
that would have required him to do his own homework and to learn something in
the process, you do it for him and teach him how to copy-paste. Perhaps when
he graduates and can't code anything, he can come work where you work, and
you'll still be so kind as to do his work for him, while he sits back and
collects a paycheck.

Bah!

-n

why should we care?

 

[Nikolaos D. Bougalis]

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!
[solution to the homework problem the OP was having]

Congratulations. Instead of helping the OP, by giving him a helpful pointer
that would have required him to do his own homework and to learn something in
the process, you do it for him and teach him how to copy-paste. Perhaps when
he graduates and can't code anything, he can come work where you work, and
you'll still be so kind as to do his work for him, while he sits back and
collects a paycheck.

Bah!

-n

why should we care?

Because doing the homework of others for them doesn't help them or anyone
else in the long run, not to mention that it's generally shunned upon.

But I guess that if you're stupid enough not to realize that doing that is
bad after it's been pointed out to you, then you're too stupid to bother with
altogether. Welcome to the killfile.

-n

 

[azi.stdout]

Because doing the homework ....

how do I know it's his homework? Should I be paranoid and try to
inspect each question somebody asks?
And what if someone asks out of couriosity... how does it differ?
You're arguing about the inpact on his job place.. Do you think, that
leaving him without an answer will improve his uninterested skills?

of others for them doesn't help them or anyone else in the long run, not to mention that it's generally shunned > upon.

How does it help when we answer a question to somone that posed it out
of couriosity?

But I guess that if you're stupid enough not to realize that doing that is
bad after it's been pointed out to you, then you're too stupid to bother with
altogether.

it looks like I'm too stupid then. I don't see how can it damage our
society if we help someone not interesting in his homework, he'll
definately not be more interested after a long google blame, or
whatever.


Ps. You shoud send a mail to google to prohibit the use of the code
search engine, or at last, to trust only users with no homework
assigmens.

 

[dcorbit]

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!

http://mathworld.wolfram.com/TotientFunction.html

 

[toby]

how do I know it's his homework? Should I be paranoid and try to
inspect each question somebody asks?
And what if someone asks out of couriosity... how does it differ?
You're arguing about the inpact on his job place.. Do you think, that
leaving him without an answer will improve his uninterested skills?

Yes.

Did you ask on Usenet for the answers to your study questions? It's
reflective of an inability to self-locate answers, and worse,
indicative of a strong disinterest in learning.

How does it help when we answer a question to somone that posed it out
of couriosity?

And how will you tell the difference? Either way, passive resources are
available. The fact they didn't even use them already speaks of
laziness.

it looks like I'm too stupid then. I don't see how can it damage our
society if we help someone not interesting in his homework,

See below.

he'll
definately not be more interested after a long google blame, or
whatever.


Ps. You shoud send a mail to google to prohibit the use of the code
search engine, or at last, to trust only users with no homework
assigmens.

The complaint is not about *passive* resources: We might as well ban
students from libraries, since the answers are contained there as well.
The problem is active assistance in helping someone not learn. They
copy your answer instead of going through the pedagogy of arriving at
it, completely defeating the purpose of their being at school in the
first place.