0
$\begingroup$

I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$

Let me explain myself by pointing to a brief example:

$p = 131$

$q = 11953$

$N= p*q = 1565843$

The totient defines the quantity of positive integers less or equal than $N$ coprime with $N$. So we calculate it:

$ϕ(N) = (p-1)(q-1) = 1553760$

But I have realized that this way can also be obtained:

How many multiples of p are under N? q multiples of p

How many multiples of q are under N? p multiples of q

These previous statements show the quantity of integers NOT coprime with $N$ that are less or equal to $N$. It's just the opposite of the Euler's Totient.

So the equation is the following:

$ϕ(N) = N - p - q + 1$

In the example:

$ϕ(N) = 1565843 - 131 - 11953 + 1$

$ϕ(N) = 1553760$

I suppose that this method is well documented over there. I just want to know if this is a good praxis for using in an implementation (for example).

Thanks for your time!

$\endgroup$
1
  • 1
    $\begingroup$ Yes, that trivially follows from the definition. Are you asking whether it's "better" to compute the totient as $N - p - q + 1$ instead of $(p - 1)(q - 1)$? They are always equal, of course, since $(p - 1)(q - 1) = pq - p - q + (-1)(-1) = N - p - q + 1$. $\endgroup$
    – Thomas
    Jun 2 '15 at 0:24
0
$\begingroup$

You can get the 2nd equation from the first with some simple algebra.

$$(p-1)(q-1)$$ $$pq-p-q+1$$ $$n-p-q+1$$

I'm not really sure what you are asking though. Are you asking if computing the second is faster than the first?

I suppose you could argue that you have to do the $pq$ multiplication anyways, so why not reuse it. If that is your argument, then doing the calculation with the 2nd equation you gave for $\varphi$, then you get the multiplication for free and only have to do 2 subtractions and an addition. Using the first equation, you have to do two subtractions (although only a minus 1) and one multiplication. Multiplication is much more expensive, so the 2nd equation would be more efficient.

$\endgroup$
5
  • $\begingroup$ So it comes from the 1st equation. Well I just thought it and put on paper, didn't notice. $\endgroup$
    – kub0x
    Jun 2 '15 at 0:31
  • $\begingroup$ Yes, I'm asking if this way the computation cost is lower with this way. Could you give me an explanation? $\endgroup$
    – kub0x
    Jun 2 '15 at 0:32
  • $\begingroup$ @kub0x see the updates. $\endgroup$
    – mikeazo
    Jun 2 '15 at 1:22
  • $\begingroup$ So the 2nd way is more efficient. Thank you cleared my doubt. $\endgroup$
    – kub0x
    Jun 2 '15 at 1:31
  • $\begingroup$ @kub0x, yes, I think you could make that argument. $\endgroup$
    – mikeazo
    Jun 2 '15 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.