56 lines
1.7 KiB
Python
56 lines
1.7 KiB
Python
# (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} секунд.") |