106 lines
3.5 KiB
Python
106 lines
3.5 KiB
Python
# (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 секунд. |