473,322 Members | 1,314 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Computing Euler's totient function

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 9067
"Protoman" <Pr**********@gmail.comwrites:
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.
Dec 27 '06 #2

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
Pascal Bourguignon wrote:
"Protoman" <Pr**********@gmail.comwrites:
>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/
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

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
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
Dec 27 '06 #6

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
az********@gmail.com wrote:
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?
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
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

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

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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

42
by: John Smith | last post by:
In a C program I need to do exponentiation where the base is negative and the exponent is a fraction. In standard C this would be something like t = pow(-11.5, .333), but with this combination of...
0
by: natty2006 | last post by:
Submission Deadline extended: 13 November 2006 ************************************************************* IADIS INTERNATIONAL CONFERENCE APPLIED COMPUTING 2007 February 17-20, 2007 -...
7
by: dkultasev | last post by:
Hello, could anyone help with euler circuit ? I tried to find it, found some, but they are not working. Tried to write my own one, but it supposed to be slow with big graphs because it trying all...
1
by: luna18 | last post by:
i like to do programming but i am not a computer student.. =) i m trying to write a program to determine a euler circuit.but end up all stuck... i tyr to take the input as graph and if it is a...
13
by: Xah Lee | last post by:
Today, a motherfucker Christophe Rhodes (aka Xof in irc://chat.freenode.net/lisp ) kicked banned me. Here's the few relevant excerpt. (full, unedited excerpt will be published if there is a public...
25
by: jwrweatherley | last post by:
I'm pretty new to python, but am very happy with it. As well as using it at work I've been using it to solve various puzzles on the Project Euler site - http://projecteuler.net. So far it has not...
14
by: Aaron Watters | last post by:
So, in between skiing runs I noticed a Business Week cover story on "cloud computing". The article had lots of interesting information in it like about how somebody's mom used to be an airline...
4
by: process | last post by:
I am trying to solve project euler problem 18 with brute force(I will move on to a better solution after I have done that for problem 67). http://projecteuler.net/index.php?section=problems&id=18 ...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.