# p-метод Полладра
import random
import time
from math import gcd
from utils import is_prime

log = []
def logger(i, x, y, gcd):
    global log
    if len(log) > 10: log = log[:5] + log[-5:]
    log.append(f'iter = {i}, a = {x}, b = {y}, gcd(x-y, n) = {gcd}')

def _rho_pollard(N):
    x = random.randint(1, N - 1)
    y, i, stage = 1, 0, 2
    while gcd(N, abs(x - y)) == 1:
        if i == stage:
            y = x
            stage <<= 1
        x = (x * x + 1) % N
        i += 1
        logger(i, x, y, 1)

    d = gcd(N, abs(x - y))
    return d

def rho_pollard(N):
    factors, stack = [], [N]
    while stack:
        current = stack.pop()
        if current == 1: continue
        if is_prime(current):
            factors.append(current)
            continue

        divisor = _rho_pollard(current)

        stack.append(divisor)
        stack.append(current // divisor)

    return sorted(factors)

if __name__ == '__main__':
    start_time = time.time()

    N1 = 13611197472111783959 # менее секунды
    N2 = 1191515026104746183243378937330489098579 # ~2.5 часа
    N3 = 74048093444435937986114388960912781233885985702403356033834092312625704192350369 # слишком большое, не считает

    number = N1

    fact = rho_pollard(number)
    print(f"Первые 5 записей:")
    for e in log[:5]: print(e)
    print(f"Последние 5 записей:")
    for e in log[-5:]: print(e)

    print(f"\nФакторизация числа {number}: {fact}")

    elapsed_time = time.time() - start_time
    print(f"Общее время работы программы: {elapsed_time} секунд.")

# ЧИСЛО 1
# Первые 5 записей:
# iter = 1, a = 5329095354621087087, b = 1, gcd(x-y, n) = 1
# iter = 2, a = 3783727702130089265, b = 1, gcd(x-y, n) = 1
# iter = 3, a = 7095258768956724187, b = 3783727702130089265, gcd(x-y, n) = 1  
# iter = 4, a = 12321744609163004701, b = 3783727702130089265, gcd(x-y, n) = 1 
# iter = 5, a = 12323988029058238822, b = 12321744609163004701, gcd(x-y, n) = 1
# Последние 5 записей:
# iter = 139741, a = 4060051924514528227, b = 13218681676865582158, gcd(x-y, n) = 1
# iter = 139742, a = 5345059737904245033, b = 13218681676865582158, gcd(x-y, n) = 1
# iter = 139743, a = 260418000338173485, b = 13218681676865582158, gcd(x-y, n) = 1 
# iter = 139744, a = 6264061095634053, b = 13218681676865582158, gcd(x-y, n) = 1   
# iter = 139745, a = 2327761422004049427, b = 13218681676865582158, gcd(x-y, n) = 1

# Факторизация числа 13611197472111783959: [2978457007, 4569882137]
# Общее время работы программы: 0.1660001277923584 секунд.

# ЧИСЛО 2
# Первые 5 записей:
# iter = 1, a = 108874332809547025907597843044982083159, b = 1, gcd(x-y, n) = 1
# iter = 2, a = 1097955600928184726703035165824138374896, b = 1, gcd(x-y, n) = 1
# iter = 3, a = 488285885718394315847189711962319835985, b = 1097955600928184726703035165824138374896, gcd(x-y, n) = 1
# iter = 4, a = 401360566326618042671847881691355213222, b = 1097955600928184726703035165824138374896, gcd(x-y, n) = 1
# iter = 5, a = 1156594234894495846629254317716430429392, b = 401360566326618042671847881691355213222, gcd(x-y, n) = 1
# Последние 5 записей:
# iter = 6760246676, a = 924157203270482170564225956282613146461, b = 508819885811370882496826690334047716214, gcd(x-y, n) = 1
# iter = 6760246677, a = 948491128612786337471979266549113961972, b = 508819885811370882496826690334047716214, gcd(x-y, n) = 1
# iter = 6760246678, a = 1132206947658731453064263670716458783892, b = 508819885811370882496826690334047716214, gcd(x-y, n) = 1
# iter = 6760246679, a = 320645645670504982689398810315637415969, b = 508819885811370882496826690334047716214, gcd(x-y, n) = 1
# iter = 6760246680, a = 1089717013392774221300379814430702238408, b = 508819885811370882496826690334047716214, gcd(x-y, n) = 1

# Факторизация числа 1191515026104746183243378937330489098579: [28078932453784161973, 42434484575433608423]
# Общее время работы программы: 9818.221776247025 секунд.