Inverse Euler´s Totient Calculator with Python

Euler's totient is a necessary numerical calculation for most modern primer number-based cryptographic systems. The forward calculation counts the positive integers up to a given integer n that are relatively prime to n. All the information is, for example, in the Wikipedia link: Euler's Totient Function.

Now, the complexity comes with the inverse calculation, and this is not a function as we expect more than one integer in the real number space that shares Euler's totient. This is Carmichael's Totient Function Conjecture, a fascinating read here.

So what do we do if we want to find a list of all numbers that share a given Euler's Totient? We will use python to brute force our way into this list. First of all, we need a function to evaluate if any two given numbers are coprime, that is, their GCD, Greatest Common Divisor, is one:

def gcd(a, b): 
    if (a == 0):
        return b
    return gcd(b % a, a)

With this function, we can evaluate, for a given number, how many other numbers smaller than itself fulfill the condition that their GCD is 1, phi will be our Euler's Totient:

def phi(n): 
    result = 1
    for i in range(2, n):
        if (gcd(i, n) == 1):
            result +=1
    return result

For example, the result for a prime number as 353 returns a value of 352 for the totient. For all prime numbers, its totient will be itself minus one. For 352, non-prime, the totient is 160:

n = 353
phi(n)
>> 352
n = 352
phi(n)
>> 160

Now, to find how many other numbers share 160, for example, as totient, we will need to determine the range for the maximum number that could have 160 as a totient and, sadly, check all numbers below that for coincidences in the totient value. The maximum number that has this totient must be a combination of 2 and 3 to the power of the number of times we need to recursively calculate the totient for the number until we hit a value of 1; how many "power steps" of 2 times three we need to traverse until we reach the final value. This function calculates these steps:

def find_steps(c):
  L = 0
  while True:
    c = phi(c)
    L += 1
    if c==1: break
  return 2*3**L

While our totient is not one, we keep calculating and counting how many totients we need to calculate until we reach the final value of one. The maximum number with a given totient must be a combination of 2 and 3 to the power of this number of steps. This external post shows an example of such a procedure. As an example, for a totient of 160, we should check up to 4374 for possible occurrences of this specific totient value:

t = 160
max_n = find_steps(t)
max_n
>> 4374

Wrapping all these calculations together, we can define the function that will calculate all the possible totients starting from the maximum value we can possibly have and add them to a tuple:

def inverse_tot(n):
  res = tuple()
  for i in range(find_steps(n), 0, -1):
    phi_c = phi(i)
    if phi_c == n:
      res += (i,)
  
  return res

The result for 160, all numbers with Euler's totient 160, is then:

res = inverse_tot(160)
res
>> (660, 600, 528, 492, 440, 410, 400, 374, 352, 328, 205, 187)

As a side note, the totient cannot be an odd number; our function can be improved to prevent unnecessary time wastes:

def inverse_tot(n):
  if n % 2 != 0: return tuple()
  res = tuple()
  for i in range(find_steps(n), 0, -1):
    phi_c = phi(i)
    if phi_c == n:
      res += (i,)
  
  return res

Now we are armed with an inverse Euler's Totient calculator that can improve our cryptographic work, even if the calculator is still very slow and we have no algorithmic advantage beyond brute force.

The notebook for this publication is here.

Do not hesitate to contact us if you require quantitative model development, deployment, verification, or validation. We will also be glad to help you with your machine learning or artificial intelligence challenges when applied to asset management, automation, or intelligence gathering from satellite, drone, or fixed-point imagery. Also, check our AI-Powered Spanishpublic tender search application using sentence similarity analysis to provide better tender matches to selling companies.

Euler´s Totient dreamscape by art generating artificial intelligence.