2

Based on wikipedias description about Euler's Totient Function, i wrote the following code:

from math import gcd

def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            amount += 1
    return amount

It works fine for small numbers, but i want to compute the totient function for numbers such as n = 5692297035794675412610596123456169

Is there any better way to compute the Totoent function for such as big inputs?

Peter Wood
  • 23,859
  • 5
  • 60
  • 99
mariohez
  • 31
  • 4
  • 2
    You need to use some maths. Brute force is not enough. – Peter Wood May 09 '21 at 09:06
  • If this is RSA and your large number is N = p*q where p and q are primes, then there is a very simple way to calculate totient(N). A little research will help you. – rossum May 09 '21 at 09:43
  • Big? how big? `factor(5692297035794675412610596123456169)` and `phi = (47-1) * (2819-1) * (65713-1) * (891551-1) * (57247819-1) * (12809677289-1)` – kelalaka May 09 '21 at 12:23
  • 1
    Does this answer your question? [Computing Eulers Totient Function](https://stackoverflow.com/questions/18114138/computing-eulers-totient-function) – itprorh66 May 09 '21 at 15:00
  • https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler's_product_formula – President James K. Polk May 09 '21 at 15:16

1 Answers1

2

Since this is also tagged Cryptography, this about more into the effectiveness of possible algorithms.

There is a way to compute the Euler Totient φ very fast if you know the prime factors of n. Let pi be distinct k primes factors of n then

φ(n) = (p1 -1) * (p2-1) * ... * (pk-1)

There is also a formula for prime powers, too. That is not necessary here since either RSA encryption/signature or Paillier encryption or Rabin signatures uses n = p*q with two distinct primes p and q.

As we see, effectively finding the φ(n) requires the knowledge of the factorization. It is proven that for RSA the knowledge of the φ(n) is equal to factorization of the n. Shortly see here;

or see in the original RSA paper;

If we turn to factoring (RSA), the current record achieved in 2020, CADO-NFS has factored an 828-bit n with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)".

However, if you ever need to use RSA, you should use a modulus of size at least 2048-bits, see in keylength.com. This is safe from factoring at least for a reasonable time from classical factorization and Shor's quantum factoring algorithm.

As a result, there is no effective algorithm for finding the Euler's totient for large n if you don't know the factorization.

kelalaka
  • 5,064
  • 5
  • 27
  • 44