Efficient way to compute Eulers Totient Function for big input

user_15371053 0
Viewed 503

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?

cryptography python-3.x python
1 Answers

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.

user_18205530
Related