shor.py

import random 
import math 

def mod_pow(a, x, N):
    y = 1
    while (x > 0):
        if ((x & 1) == 1):
            y = (y * a) % N
        x = x >> 1
        a = (a * a) % N
    return y

def findPeriodByModPow(N, a):
    for x in range(1, N):
#        print("x is ",x)
        if (mod_pow(a, x, N) == 1):
            print("r is ", x)
            return x
    return -1

def factorizeByShor(N):
    while(True):
        a = random.randint(2, N - 1)
        print(a," is new a")
        gcd = math.gcd(N, a)
        if (gcd != 1):
            print("found ",gcd," * ",N//gcd)
            return gcd, N // gcd
        print("finding period")
        r = findPeriodByModPow(N, a)
        if (r % 2 != 0):
            print("skipping because r is not divisible by 2")
            continue
        gcd1 = math.gcd(N, a**(r//2) + 1)
        gcd2 = math.gcd(N, a**(r//2) - 1)
        if (gcd1 == 1 or N or gcd2 == 1 or N):
            continue
        print("gcd1 is ",gcd1, " * ", gcd2)
        return gcd1, gcd2

factorizeByShor(2129 * 2131)