from random import randint

def rshor(a, P):
    """algorithme de shor: calcul de la période de (a**k)%P"""
    k = 0
    f = 1
    while True:
        k += 1
        f = pow(a, k, P)
        if f == 1:
            break
    return k  # période trouvée
 
def shor(P):
    """algorithme de shor: factorisation de P"""
    while True:
        a = randint(2, P-1)
        print("=====> Essai avec a =", a)
 
        x = pgcd(a,P)
        if x != 1:
            n1 = x
            n2 = P//n1
            print("Solution: n1 =", n1, "n2 =", n2)
            return [n1, n2]
        else:
            r = rshor(a, P)  # calcul de la periode de f(k) = (a**k)%P par la fonction separee rshor()
            print("période r =", r)
 
            if r&1 != 1:
                print ("calcul de a**(r//2)")
                x = pow(a, r//2)
                if x%P!=1:
                    print ("calcul de n1")
                    n1 = pgcd(x+1, P)  #n1 = pgcd(a**(r//2)+1, P)
                    print ("calcul de n2")
                    n2 = pgcd(x-1, P)  #n2 = pgcd(a**(r//2)-1, P)
                    if (n1!=1) and (n2!=1):
                        print ("Solution: n1=", n1, "n2=", n2)
                        return [n1, n2]
            # si on arrive ici, on boucle pour essayer un autre "a"
            
def pgcd(a,b):
    """pgcd(a,b): calcul du 'PGCD' entre les 2 nombres entiers a et b"""
    a, b = abs(a), abs(b)
    while b:
        r = a%b
        a, b = b, r
    return a

shor(1010101010101)