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

def _rho_minus_1_pollard(n, 
                         B_start=100, 
                         B_step=10, 
                         B_max=100000000):
    B = B_start
    while B <= B_max:
        a = 2
        for p in primes(B):
            pp = 1
            while pp * p <= B:
                pp *= p
            a = pow(a, pp, n)
            g = gcd(a - 1, n)
            if 1 < g < n:
                return g, B
        B *= B_step
    return None, B_max

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"Факторизация числа {number}: {factors}")

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