# (p-1)-алгоритм Полларда, реализация _rho_minus_1_pollard по алгосу из презентации препода
import time
from math import gcd, log as ln
from utils import is_prime, primes
import random

log = []
def logger(i, p, l, b):
    global log
    if len(log) > 10: log = log[:5] + log[-5:]
    log.append(f'iter = {i}, p_i = {p}, l_i = {l}, B = {b}')

def _rho_minus_1_pollard(n, 
                         B_start=100, 
                         B_step=10, 
                         B_max=100000000):
    i, B = 0, B_start
    while B <= B_max:
        a = random.randint(2, n - 1)
        d = gcd(a, n)
        if d >= 2: return d
        for p in primes(B):
            l = int(ln(n)/ln(p))
            a = pow(a, p**l, n)

            i += 1
            logger(i, p, l, B)

        d = gcd(a-1, n)
        if not (d == 1 or d == n): 
            return d
        B *= B_step
        
    return None

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

        divisor = _rho_minus_1_pollard(current)
        if divisor is None:
            factors.append(current)
            continue

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

    return sorted(factors)

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

    N1 = 13611197472111783959 # менее тысячной доли секунды
    N2 = 1191515026104746183243378937330489098579 # менее трех десятых секунд
    N3 = 74048093444435937986114388960912781233885985702403356033834092312625704192350369 # не считается

    number = N1

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

    elapsed_time = time.time() - start_time
    print(f"\nФакторизация числа {number}: {factors}")
    print(f"Общее время работы программы: {elapsed_time} секунд.")

# ЧИСЛО 1
# Первые 5 записей:
# iter = 1, p_i = 2, l_i = 63, B = 100
# iter = 2, p_i = 3, l_i = 40, B = 100
# iter = 3, p_i = 5, l_i = 27, B = 100
# iter = 4, p_i = 7, l_i = 22, B = 100
# iter = 5, p_i = 11, l_i = 18, B = 100
# Последние 5 записей:
# iter = 21, p_i = 73, l_i = 10, B = 100
# iter = 22, p_i = 79, l_i = 10, B = 100
# iter = 23, p_i = 83, l_i = 9, B = 100
# iter = 24, p_i = 89, l_i = 9, B = 100
# iter = 25, p_i = 97, l_i = 9, B = 100

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

# ЧИСЛО 2
# Первые 5 записей:
# iter = 1, p_i = 2, l_i = 129, B = 100
# iter = 2, p_i = 3, l_i = 81, B = 100
# iter = 3, p_i = 5, l_i = 55, B = 100
# iter = 4, p_i = 7, l_i = 46, B = 100
# iter = 5, p_i = 11, l_i = 37, B = 100
# Последние 5 записей:
# iter = 11010, p_i = 99929, l_i = 7, B = 100000
# iter = 11011, p_i = 99961, l_i = 7, B = 100000
# iter = 11012, p_i = 99971, l_i = 7, B = 100000
# iter = 11013, p_i = 99989, l_i = 7, B = 100000
# iter = 11014, p_i = 99991, l_i = 7, B = 100000

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