import random 
import math 

def mod_pow(a, x, N):
    y = 1
    while (x > 0):
        if ((x & 1) == 1):   # x & 1은 x의 가장 오른쪽 비트(최하위 비트)를 검사하는 연산이다. 즉 홀수인지 짝수인지 판별한다.
            y = (y * a) % N
        x = x >> 1   # 비트 시프트 연산자, 2로 나누고 소수점 버림(정수 나눗셈)과 같음.
        a = (a * a) % N   
    return y

def findPeriodByModPow(N, a):
    for x in range(1, N):
        if (mod_pow(a, x, N) == 1):
            return x
    return -1

def factorizeByShor(N):
    while True:
        a = random.randint(2, N - 1)   # 2와 N-1 사이의 랜덤한 정수
        gcd = math.gcd(N, a)   # N과 a의 최대공약수를 구한다.
        if (gcd != 1):   # N과 a의 최대공약수가 1이 아니라면
            return gcd, N // gcd   # N//gcd N을 gcd로 나누고 소수점을 버린 값. "정수 나눗셈"
        r = findPeriodByModPow(N, a)
        if (r % 2 != 0):
            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
        return gcd1, gcd2

# 인수분해 할 숫자 입력
password = 110489
# 110489 = 313 * 353

gcd1, gcd2 = factorizeByShor(password)

print(f"password = {password} = {gcd1} x {gcd2}")