454,128 Members | 926 Online
Need help? Post your question and get tips & solutions from a community of 454,128 IT Pros & Developers. It's quick & easy.

# Computing Euler's totient function

 P: n/a 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! Dec 27 '06 #1
10 Replies

 P: n/a "Protoman"

 P: n/a 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! 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. Dec 27 '06 #3

 P: n/a Pascal Bourguignon wrote: "Protoman" Hi! I'm trying to compute Euler's totient function for an extremelysimple RSA program I'm writing. How, exactly, is it calculated? 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=E...l=en&btnG=Code Dec 27 '06 #4

 P: n/a 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 Dec 27 '06 #5

 P: n/a st****@gmail.com wrote: > >Hi! I'm trying to compute Euler's totient function for an extremelysimple 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 Dec 27 '06 #6

 P: n/a Nikolaos D. Bougalis wrote: st****@gmail.com 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! [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? Dec 27 '06 #7

 P: n/a az********@gmail.com wrote: Nikolaos D. Bougalis wrote: >st****@gmail.com wrote: >>>Hi! I'm trying to compute Euler's totient function for an extremelysimple 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 pointerthat would have required him to do his own homework and to learn something inthe process, you do it for him and teach him how to copy-paste. Perhaps whenhe graduates and can't code anything, he can come work where you work, andyou'll still be so kind as to do his work for him, while he sits back andcollects 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 Dec 27 '06 #8

 P: n/a 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. Dec 27 '06 #9

 P: n/a 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! http://mathworld.wolfram.com/TotientFunction.html Dec 27 '06 #10

 P: n/a az********@gmail.com wrote: 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? 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. > 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? 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. > 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, 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. Dec 28 '06 #11

### This discussion thread is closed

Replies have been disabled for this discussion.