I create an algorithm for totient detection for large number, actually this work well with number like 2^64 but for more, the variable g substract to phi_a slow down, because the bit’s length of large number as become more larger, bit lenght is not proportionnal and larger number increase slower the bitlength of g and the step of g (or usage of bit length) become slow down. Can you find a better way to larger g as the n number in entry become larger ? Thanks for all answers.

import gmpy2

def optimized_phi_calculation():
    # Initialisation des constantes
    p = 11
    q = 23
    n = p * q
    phi_t = (p - 1) * (q - 1) // 2
    s = gmpy2.isqrt(n)
    phi_a = (n - 2 * s) // 2
    count = 0

    powmod = gmpy2.powmod
    bit_length = gmpy2.bit_length

    while True:
        count += 1
        if phi_a < phi_t:
          break
        x = powmod(2, phi_a, n)

        # Vérification si x est une puissance de 2
        if x != 0 and (x & (x - 1)) == 0:
            g = bit_length(x)-1
            print(phi_t, phi_a - g, g, count)
            break
        else:
            # Utilisation de bit_length pour calculer l'exposant g
            g = bit_length(x)
            phi_a -= g
            

# Appel de la fonction optimisée
optimized_phi_calculation()