95 lines
4.1 KiB
Python
95 lines
4.1 KiB
Python
# 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 секунд. |