-- coding: utf-8 --
"""
Barantic v0.3 - Recursive Parallel Smooth Fermat Factorization (RSA-100 tuned)
- Recursive factorization: P(n) = n // 2 tabanlı prime listesi
- P kademeli: 10, 20, 40, 80, 120, 160, 200 asal ile denenir
- Default max_workers = 10
- Max recursion depth = 5
- Miller-Rabin primality test
- Safe P calculation:
- MAX_SIEVE = 1_000_000
- calculate_P_from_input için en fazla SAFE_PRIME_COUNT (200) asal
- Genişletilmiş adım limitleri ve büyük N için:
- 80+ basamaklı sayılarda her worker için max 10,000,000 adım """
import math
import random
import time
import sys
from typing import Optional, Tuple, List, Dict
from multiprocessing import cpu_count
import concurrent.futures
Python 3.11+ integer string limitini kaldır (büyük sayıları rahat yazdırabilmek için)
if hasattr(sys, "set_int_max_str_digits"):
sys.set_int_max_str_digits(0)
============================================================
Sabitler
============================================================
MAX_SIEVE = 1_000_000 # primes_up_to için üst limit
SAFE_PRIME_COUNT = 200 # calculate_P_from_input için maksimum asal sayısı
MAX_RECURSION_DEPTH = 5 # Recursive faktorizasyon derinliği
DEFAULT_MAX_WORKERS = 10 # Varsayılan paralel worker sayısı
MAX_STEPS_PER_WORKER = 10_000_000 # Her işlemci için maksimum adım sayısı
============================================================
Temel Matematik Fonksiyonları
============================================================
def gcd(a: int, b: int) -> int:
"""Klasik Euclid GCD"""
while b:
a, b = b, a % b
return abs(a)
def is_probable_prime(n: int) -> bool:
"""Miller-Rabin probable prime testi (deterministic for 64-bit+, pratikte güvenli)"""
if n < 2:
return False
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
for p in small_primes:
if n == p:
return True
if n % p == 0:
return n == p
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
# Sabit taban seti (64-bit bölgesi için yeterli)
for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
if a % n == 0:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
witness = True
for _ in range(s - 1):
x = (x * x) % n
if x == n - 1:
witness = False
break
if witness:
return False
return True
def primes_up_to(n: int) -> List[int]:
"""
Basit Eratosthenes Sieve.
MAX_SIEVE ile sınırlandırıldı ki P_input çok büyük olduğunda overflow/memory patlaması olmasın.
"""
if n < 2:
return []
if n > MAX_SIEVE:
n = MAX_SIEVE
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(n ** 0.5) + 1):
if sieve[i]:
step = i
start = i * i
sieve[start:n + 1:step] = [False] * (((n - start) // step) + 1)
return [i for i, v in enumerate(sieve) if v]
def primes_in_range(lo: int, hi: int) -> List[int]:
if hi < 2 or hi < lo:
return []
ps = primes_up_to(hi)
return [p for p in ps if p >= max(2, lo)]
def fermat_factor_with_timeout(
n: int,
time_limit_sec: float = 30.0,
max_steps: int = 0
) -> Optional[Tuple[int, int, int]]:
"""
Basit Fermat faktorizasyonu (timeout ve max_steps ile).
Dönüş: (x, y, steps) öyle ki x*y = n
"""
if n <= 1:
return None
if n % 2 == 0:
return (2, n // 2, 0)
start = time.time()
a = math.isqrt(n)
if a * a < n:
a += 1
steps = 0
while True:
if max_steps and steps > max_steps:
return None
if time.time() - start > time_limit_sec:
return None
b2 = a * a - n
if b2 >= 0:
b = int(math.isqrt(b2))
if b * b == b2:
x = a - b
y = a + b
if x * y == n and x > 1 and y > 1:
return (x, y, steps)
a += 1
steps += 1
def pollard_rho(n: int, time_limit_sec: float = 10.0) -> Optional[int]:
"""Klasik Pollard-Rho faktorlama"""
if n % 2 == 0:
return 2
if is_probable_prime(n):
return n
start = time.time()
while time.time() - start < time_limit_sec:
c = random.randrange(1, n - 1)
f = lambda x: (x * x + c) % n
x = random.randrange(2, n - 1)
y = x
d = 1
while d == 1 and time.time() - start < time_limit_sec:
x = f(x)
y = f(f(y))
d = gcd(abs(x - y), n)
if 1 < d < n:
return d
return None
def modinv(a: int, n: int) -> Tuple[Optional[int], int]:
"""Modüler ters (extended Euclid)"""
a = a % n
if a == 0:
return (None, n)
r0, r1 = n, a
s0, s1 = 1, 0
t0, t1 = 0, 1
while r1 != 0:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
if r0 != 1:
return (None, r0)
return (t0 % n, 1)
def ecm_stage1(
n: int,
B1: int = 10000,
curves: int = 50,
time_limit_sec: float = 5.0
) -> Optional[int]:
"""
ECM Stage1 (hafif versiyon). Büyük faktörler için yardımcı.
"""
if n % 2 == 0:
return 2
if is_probable_prime(n):
return n
start = time.time()
# prime powers up to B1
smalls = primes_up_to(B1)
prime_powers = []
for p in smalls:
e = 1
while p ** (e + 1) <= B1:
e += 1
prime_powers.append(p ** e)
def ec_add(P, Q, a, n):
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and (y1 + y2) % n == 0:
return None # point at infinity
if x1 == x2 and y1 == y2:
num = (3 * x1 * x1 + a) % n
den = (2 * y1) % n
else:
num = (y2 - y1) % n
den = (x2 - x1) % n
inv, g = modinv(den, n)
if inv is None:
if 1 < g < n:
raise ValueError(g)
return None
lam = (num * inv) % n
x3 = (lam * lam - x1 - x2) % n
y3 = (lam * (x1 - x3) - y1) % n
return (x3, y3)
def ec_mul(k, P, a, n):
R = None
Q = P
while k > 0:
if k & 1:
R = ec_add(R, Q, a, n)
Q = ec_add(Q, Q, a, n)
k >>= 1
return R
while time.time() - start < time_limit_sec and curves > 0:
x = random.randrange(2, n - 1)
y = random.randrange(2, n - 1)
a = random.randrange(1, n - 1)
b = (pow(y, 2, n) - (pow(x, 3, n) + a * x)) % n
disc = (4 * pow(a, 3, n) + 27 * pow(b, 2, n)) % n
g = gcd(disc, n)
if 1 < g < n:
return g
P = (x, y)
try:
for k in prime_powers:
P = ec_mul(k, P, a, n)
if P is None:
break
except ValueError as e:
g = int(str(e))
if 1 < g < n:
return g
curves -= 1
return None
============================================================
Adım Sayısı Hesabı (Genişletilmiş Limitler)
============================================================
def square_proximity(n: int) -> Tuple[int, int]:
"""Return (a, gap) where a=ceil(sqrt(n)), gap=a^2 - n."""
a = math.isqrt(n)
if a * a < n:
a += 1
gap = a * a - n
return a, gap
def calculate_enhanced_adaptive_max_steps(
N: int,
P: int,
is_parallel: bool = True,
num_workers: int = 1
) -> int:
"""
Geliştirilmiş max_steps hesaplama (paralel için uygun ölçekleme).
Bu sürümde:
- Küçük/orta N için önceki adaptif davranış
- 80+ basamaklı N'ler için: her worker max 10M adım hedefi
"""
digits = len(str(N))
# Base steps scaling by digits (paralel için)
if is_parallel:
if digits <= 20:
base_steps = 50_000
elif digits <= 30:
base_steps = 100_000
elif digits <= 40:
base_steps = 200_000
elif digits <= 50:
base_steps = 500_000
elif digits <= 60:
base_steps = 1_000_000
elif digits <= 70:
base_steps = 2_000_000
elif digits <= 80:
base_steps = 5_000_000
elif digits <= 90:
base_steps = 10_000_000
else:
base_steps = 20_000_000
else:
# Single-threaded daha muhafazakâr
if digits <= 30:
base_steps = 10_000
elif digits <= 50:
base_steps = 50_000
elif digits <= 70:
base_steps = 200_000
else:
base_steps = 500_000
# Square gap analizi
_, gap_N = square_proximity(N)
M = N * P
_, gap_M = square_proximity(M)
if gap_N > 0:
gap_ratio = gap_M / gap_N
if gap_ratio > 1e20:
gap_factor = 0.3
elif gap_ratio > 1e15:
gap_factor = 0.5
elif gap_ratio > 1e12:
gap_factor = 0.7
elif gap_ratio > 1e8:
gap_factor = 1.0
else:
gap_factor = 2.0
else:
gap_factor = 1.0
# P etkinlik faktörü
P_digits = len(str(P))
if P_digits >= 25:
p_factor = 0.4
elif P_digits >= 20:
p_factor = 0.6
elif P_digits >= 15:
p_factor = 0.8
else:
p_factor = 1.2
# Paralel worker ölçekleme
if is_parallel and num_workers > 1:
worker_factor = max(0.5, 1.0 - (num_workers - 1) * 0.05)
else:
worker_factor = 1.0
adaptive_steps = int(base_steps * gap_factor * p_factor * worker_factor)
# Yeni limitler (80+ basamaklılar için worker başına 10M)
if is_parallel:
if digits >= 80:
min_steps = MAX_STEPS_PER_WORKER
else:
min_steps = max(10_000, digits * 500)
max_steps_limit = min(50_000_000, digits * 500_000, MAX_STEPS_PER_WORKER)
else:
min_steps = max(1_000, digits * 100)
max_steps_limit = min(10_000_000, digits * 200_000)
adaptive_steps = max(min_steps, min(adaptive_steps, max_steps_limit))
return adaptive_steps
============================================================
Smooth Fermat Temel Fonksiyonları
============================================================
def divide_out_P_from_factors(
A: int,
B: int,
P: int,
primesP: List[int]
) -> Tuple[int, int]:
"""P çarpanlarını A veya B'den bölüp çıkarma."""
remP = P
for p in primesP:
if remP % p == 0:
if A % p == 0:
A //= p
remP //= p
elif B % p == 0:
B //= p
remP //= p
return A, B
def factor_with_smooth_fermat(
N: int,
P: int,
P_primes: List[int],
time_limit_sec: float = 60.0,
max_steps: int = 0,
rho_time: float = 10.0,
ecm_time: float = 10.0,
ecm_B1: int = 20000,
ecm_curves: int = 60
) -> Optional[Tuple[List[int], dict]]:
"""
Smooth Fermat faktorizasyonu (tek işlemci versiyonu).
max_steps verilmezse, gelişmiş adaptive hesap kullanılır.
"""
if N <= 1:
return None
if max_steps <= 0:
max_steps = calculate_enhanced_adaptive_max_steps(N, P, is_parallel=False)
M = N * P
t0 = time.time()
res = fermat_factor_with_timeout(M, time_limit_sec=time_limit_sec, max_steps=max_steps)
t1 = time.time()
stats = {
"method": "enhanced_adaptive_smooth_fermat",
"time": t1 - t0,
"ok": False,
"max_steps_used": max_steps
}
if res is None:
return None
A, B, steps = res
stats["steps"] = steps
A2, B2 = divide_out_P_from_factors(A, B, P, P_primes)
if A2 * B2 != N:
g = gcd(A, N)
if 1 < g < N:
A2 = g
B2 = N // g
else:
g = gcd(B, N)
if 1 < g < N:
A2 = g
B2 = N // g
else:
return None
stats["ok"] = True
# A2 ve B2 yi daha fazla parçalamayı dene
factors = []
for x in [A2, B2]:
if x == 1:
continue
if is_probable_prime(x):
factors.append(x)
continue
d = pollard_rho(x, time_limit_sec=rho_time)
if d is None:
d = ecm_stage1(x, B1=ecm_B1, curves=ecm_curves, time_limit_sec=ecm_time)
if d is None or d == x:
rf = fermat_factor_with_timeout(x, time_limit_sec=min(5.0, time_limit_sec), max_steps=max_steps)
if rf is None:
factors.append(x)
else:
a, b, _ = rf
for y in (a, b):
if is_probable_prime(y):
factors.append(y)
else:
d2 = pollard_rho(y, time_limit_sec=rho_time / 2)
if d2 and d2 != y:
factors.extend([d2, y // d2])
else:
factors.append(y)
else:
z1, z2 = d, x // d
for z in (z1, z2):
if is_probable_prime(z):
factors.append(z)
else:
d3 = pollard_rho(z, time_limit_sec=rho_time / 2)
if d3 and d3 != z:
factors.extend([d3, z // d3])
else:
factors.append(z)
factors.sort()
return factors, stats
def factor_prime_list(factors: List[int]) -> List[int]:
"""
Basit son düzeltme: küçük kompozitleri Pollard-Rho ile parçalamayı dener.
"""
out = []
for f in factors:
if f == 1:
continue
if is_probable_prime(f):
out.append(f)
else:
d = pollard_rho(f, time_limit_sec=5.0)
if d and 1 < d < f:
out.extend([d, f // d])
else:
out.append(f)
return sorted(out)
============================================================
Paralel Şapka: Worker ve Parallel Wrapper
============================================================
def smooth_fermat_worker(args) -> Optional[Tuple[List[int], Dict]]:
"""
Paralel worker, her worker için farklı max_steps ve parametre seçer.
"""
(
N, P, P_primes, worker_id,
time_limit, base_max_steps, num_workers,
rho_time, ecm_time, ecm_B1, ecm_curves
) = args
random.seed(worker_id * 12345 + int(time.time() * 1000) % 10000)
worker_variation = 0.7 + 0.6 * random.random() # 0.7x ~ 1.3x
worker_steps = int(base_max_steps * worker_variation)
digits = len(str(N))
min_worker_steps = max(5000, digits * 200)
worker_steps = max(min_worker_steps, worker_steps)
# Her iş parçacığı için üst sınır: 10M adım
if worker_steps > MAX_STEPS_PER_WORKER:
worker_steps = MAX_STEPS_PER_WORKER
worker_rho_time = max(2.0, rho_time + random.uniform(-1.0, 1.0))
worker_ecm_time = max(2.0, ecm_time + random.uniform(-1.0, 1.0))
worker_ecm_curves = max(10, int(ecm_curves + random.randint(-10, 10)))
worker_ecm_B1 = max(1000, int(ecm_B1 + random.randint(-1000, 1000)))
return factor_with_smooth_fermat(
N, P, P_primes,
time_limit_sec=time_limit,
max_steps=worker_steps,
rho_time=worker_rho_time,
ecm_time=worker_ecm_time,
ecm_B1=worker_ecm_B1,
ecm_curves=worker_ecm_curves
)
def parallel_enhanced_adaptive_smooth_fermat(
N: int,
P: int,
P_primes: List[int],
time_limit_sec: float = 60.0,
max_steps: int = 0,
max_workers: int = None,
rho_time: float = 10.0,
ecm_time: float = 10.0,
ecm_B1: int = 20000,
ecm_curves: int = 60
) -> Optional[Tuple[List[int], Dict]]:
"""
Enhanced parallel smooth Fermat (Barantic çekirdeği).
Eski v0.2 çıktıları korunuyor.
"""
if max_workers is None:
max_workers = min(cpu_count(), DEFAULT_MAX_WORKERS)
else:
max_workers = max(1, min(max_workers, cpu_count()))
# Paralel için enhanced max_steps
if max_steps <= 0:
adaptive_steps = calculate_enhanced_adaptive_max_steps(N, P, is_parallel=True, num_workers=max_workers)
else:
digits = len(str(N))
min_parallel_steps = max(10_000, digits * 300)
adaptive_steps = max(max_steps, min_parallel_steps)
# İşçi başına beklenen adım aralığını (ve 10M üst sınırı) logla
est_min = max(5_000, int(adaptive_steps * 0.7))
est_max = min(MAX_STEPS_PER_WORKER, int(adaptive_steps * 1.3))
print(f" Starting enhanced parallel smooth Fermat:")
print(f" Workers: {max_workers}")
print(f" Enhanced adaptive max steps: {adaptive_steps:,}")
print(f" Time limit: {time_limit_sec}s")
print(f" Steps per worker: ~{est_min:,} to ~{est_max:,}")
tasks = []
for worker_id in range(max_workers):
tasks.append((
N, P, P_primes, worker_id,
time_limit_sec, adaptive_steps, max_workers,
rho_time, ecm_time, ecm_B1, ecm_curves
))
start_time = time.time()
try:
with concurrent.futures.ProcessPoolExecutor(max_workers=max_workers) as executor:
future_to_worker = {
executor.submit(smooth_fermat_worker, task): i
for i, task in enumerate(tasks)
}
for future in concurrent.futures.as_completed(future_to_worker, timeout=time_limit_sec + 5):
worker_id = future_to_worker[future]
try:
result = future.result()
if result is not None:
elapsed = time.time() - start_time
factors, stats = result
stats['worker_id'] = worker_id
stats['parallel_time'] = elapsed
stats['total_workers'] = max_workers
stats['base_max_steps'] = adaptive_steps
print(f" SUCCESS by worker {worker_id} in {elapsed:.6f}s")
print(f" Steps used: {stats.get('steps', 0):,}/{stats.get('max_steps_used', adaptive_steps):,}")
for f in future_to_worker:
f.cancel()
return factors, stats
except Exception as e:
print(f" Worker {worker_id} error: {e}")
continue
except concurrent.futures.TimeoutError:
print(f" Parallel processing timed out after {time_limit_sec}s")
except Exception as e:
print(f" Parallel processing error: {e}")
print(" Falling back to single-threaded...")
single_steps = calculate_enhanced_adaptive_max_steps(N, P, is_parallel=False)
return factor_with_smooth_fermat(N, P, P_primes, time_limit_sec, single_steps,
rho_time, ecm_time, ecm_B1, ecm_curves)
return None
============================================================
P Hesabı (Safe P Calculation)
============================================================
def calculate_P_from_input(P_input: str) -> Tuple[int, List[int]]:
"""
Kullanıcıdan gelen P tanımından P ve asal listesini üretir.
Güvenli hale getirildi:
- primes_up_to(...) veya primes_in_range(...) çok sayıda asal üretirse,
sadece ilk SAFE_PRIME_COUNT (200) asal alınır.
"""
P_input = P_input.strip()
if '-' in P_input:
lo, hi = map(int, P_input.split('-', 1))
primes_P = primes_in_range(lo, hi)
elif ',' in P_input:
primes_P = [int(x.strip()) for x in P_input.split(',')]
for p in primes_P:
if not is_probable_prime(p):
raise ValueError(f"{p} is not prime")
else:
upper_bound = int(P_input)
primes_all = primes_up_to(upper_bound)
if len(primes_all) > SAFE_PRIME_COUNT:
primes_P = primes_all[:SAFE_PRIME_COUNT]
print(f" [Safe P] upper_bound={upper_bound} produced {len(primes_all)} primes, taking first {SAFE_PRIME_COUNT}.")
else:
primes_P = primes_all
if len(primes_P) > SAFE_PRIME_COUNT:
primes_P = primes_P[:SAFE_PRIME_COUNT]
print(f" [Safe P] prime list truncated to first {SAFE_PRIME_COUNT} primes.")
P = 1
for p in primes_P:
P *= p
return P, primes_P
============================================================
Ana Wrapper (tek çağrıda factoring), recursive olmadan
============================================================
def factor_with_enhanced_parallel_smooth_fermat(
N: int,
P_input: str,
max_workers: int = DEFAULT_MAX_WORKERS,
time_limit_sec: float = 60.0,
max_steps: int = 0,
rho_time: float = 10.0,
ecm_time: float = 10.0,
ecm_B1: int = 20000,
ecm_curves: int = 60
) -> Dict:
"""
Kullanıcı P_input belirleyerek Barantic çalıştırır (v0.2 davranışı).
v0.3'te recursive factoring için ayrıca recursive_barantic_factor fonksiyonu var.
"""
P, P_primes = calculate_P_from_input(P_input)
result = {
'N': N,
'P': P,
'P_primes': P_primes,
'P_input': P_input,
'digits': len(str(N)),
'P_digits': len(str(P)),
'success': False,
'factors': None,
'method': None,
'time': 0,
'steps': None,
'max_steps_used': 0,
'workers_used': 0
}
print(f"\nEnhanced Parallel Smooth Fermat Factorization:")
print(f" N = {N} ({len(str(N))} digits)")
print(f" P_input = {P_input}")
print(f" P = {P} ({len(str(P))} digits)")
print(f" P_primes (len={len(P_primes)}): {P_primes}")
_, gap_N = square_proximity(N)
M = N * P
_, gap_M = square_proximity(M)
gap_ratio = gap_M / gap_N if gap_N > 0 else float('inf')
if max_workers == 1:
adaptive_steps = calculate_enhanced_adaptive_max_steps(N, P, is_parallel=False)
else:
adaptive_steps = calculate_enhanced_adaptive_max_steps(N, P, is_parallel=True, num_workers=max_workers)
print(f" Square gap N: {gap_N:,}")
print(f" Square gap M: {gap_M:,}")
print(f" Gap ratio: {gap_ratio:.2e}")
print(f" Enhanced adaptive max steps: {adaptive_steps:,}")
start_time = time.time()
if max_workers == 1:
print(" Using single-threaded enhanced adaptive algorithm")
sf_result = factor_with_smooth_fermat(
N, P, P_primes,
time_limit_sec=time_limit_sec,
max_steps=adaptive_steps,
rho_time=rho_time,
ecm_time=ecm_time,
ecm_B1=ecm_B1,
ecm_curves=ecm_curves
)
if sf_result:
factors, stats = sf_result
stats['parallel_time'] = stats['time']
stats['total_workers'] = 1
else:
sf_result = parallel_enhanced_adaptive_smooth_fermat(
N, P, P_primes,
time_limit_sec=time_limit_sec,
max_steps=max_steps if max_steps > 0 else adaptive_steps,
max_workers=max_workers,
rho_time=rho_time,
ecm_time=ecm_time,
ecm_B1=ecm_B1,
ecm_curves=ecm_curves
)
if sf_result:
factors, stats = sf_result
# Eski davranış: Pollard/ECM ile biraz daha parçala
factors_final = factor_prime_list(factors)
result['success'] = True
result['factors'] = factors_final
result['method'] = 'Enhanced Parallel Smooth Fermat'
result['time'] = stats.get('parallel_time', stats['time'])
result['steps'] = stats.get('steps')
result['max_steps_used'] = stats.get('max_steps_used', adaptive_steps)
result['workers_used'] = stats.get('total_workers', 1)
print(f"\n✓ SUCCESS!")
print(f" Raw factors: {factors}")
print(f" Final factors (after Pollard/ECM): {factors_final}")
print(f" Time: {result['time']:.6f}s")
print(f" Steps used: {result['steps']:,}/{result['max_steps_used']:,}")
print(f" Workers: {result['workers_used']}")
if result['max_steps_used'] > 0 and result['steps'] is not None:
print(f" Step efficiency: {(result['steps'] / result['max_steps_used'] * 100):.1f}%")
product = 1
for f in factors_final:
product *= f
if product == N:
print(f" ✓ Verification passed!")
else:
print(f" ✗ Verification failed! Product: {product}")
result['success'] = False
else:
result['time'] = time.time() - start_time
print(f"\n✗ FAILED after {result['time']:.2f}s")
return result
============================================================
YENİ: Recursive Barantic (P(n) = n // 2, kademeli P)
============================================================
def recursive_barantic_factor(
N: int,
max_workers: int = DEFAULT_MAX_WORKERS,
max_recursion: int = MAX_RECURSION_DEPTH,
_depth: int = 0
) -> List[int]:
"""
Barantic recursive factoring:
- P(n) = n // 2 tabanlı prime listesi kullanır
- P'yi "en küçük 10 asal" ile başlatır ve kademeli olarak artırır:
10, 20, 40, 80, 120, 160, 200 asala kadar
- max_recursion derinliğine kadar tekrar tekrar çağrılır
- Her P denemesinde Barantic çekirdeği (parallel_enhanced_adaptive_smooth_fermat) çalışır
"""
if N <= 1:
return []
if is_probable_prime(N) or _depth >= max_recursion:
return [N]
digits = len(str(N))
if digits <= 40:
time_limit = 30.0
elif digits <= 60:
time_limit = 60.0
elif digits <= 80:
time_limit = 120.0
else:
time_limit = 300.0
print("\n" + "=" * 70)
print(f"[Recursive depth={_depth}] Factoring n = {N} ({digits} digits) with P(n) = n // 2")
print("=" * 70)
# P(n) = n // 2 → hedef üst sınır
P_target = N // 2
# Safe prime list: P_target veya MAX_SIEVE'e kadar olan asallar
if P_target <= MAX_SIEVE:
all_primes = primes_up_to(P_target)
else:
all_primes = primes_up_to(MAX_SIEVE)
print(f" [Recursive Safe P] P_target={P_target} > {MAX_SIEVE}, using primes up to {MAX_SIEVE}.")
if not all_primes:
print(f" [depth={_depth}] No primes available for P construction, returning N.")
return [N]
print(f" [Recursive Safe P] total primes available: {len(all_primes)}")
# P için kullanılacak asal sayıları: 10, 20, 40, 80, 120, 160, 200 (mevcut prime sayısıyla sınırla)
candidate_counts_base = [10, 20, 40, 80, 120, 160, 200]
candidate_counts = sorted({c for c in candidate_counts_base if c <= len(all_primes)})
if not candidate_counts:
candidate_counts = [len(all_primes)]
best_raw_factors: Optional[List[int]] = None
best_stats: Optional[Dict] = None
for count in candidate_counts:
P_primes = all_primes[:count]
# P'yi oluştur
P = 1
for p in P_primes:
P *= p
# P'nin basamak sayısını yaklaşık hesapla, çok büyükse sayının kendisini yazma
P_digits_est = int(P.bit_length() * math.log10(2)) + 1 if P > 0 else 1
print(f" [Recursive P attempt] using first {count} primes -> P ≈ {P_digits_est} digits")
# Barantic çekirdeği (eski loglar burada aynen görünecek)
sf_result = parallel_enhanced_adaptive_smooth_fermat(
N, P, P_primes,
time_limit_sec=time_limit,
max_steps=0,
max_workers=max_workers,
rho_time=10.0,
ecm_time=10.0,
ecm_B1=100000,
ecm_curves=200
)
if not sf_result:
print(f" [depth={_depth}] P attempt with {count} primes failed (no factor found). Trying larger P...")
continue
raw_factors, stats = sf_result
print(f" [depth={_depth}] Raw factors from Barantic (using {count} primes): {raw_factors}")
# Trivial mi? Sadece N ve/veya 1'ler varsa ilerleme yok demektir
non_trivial = [f for f in raw_factors if f not in (1, N)]
if not non_trivial:
print(f" [depth={_depth}] Only trivial factorization (N itself). Trying larger P...")
continue
# Buraya geldiysek, bu P denemesiyle non-trivial faktör elde edildi
best_raw_factors = raw_factors
best_stats = stats
break
# Hiçbir P denemesi non-trivial faktör veremediyse, bu derinlikte N'yi olduğu gibi döndür
if best_raw_factors is None:
print(f" [depth={_depth}] All P attempts failed, returning N as composite.")
return [N]
raw_factors = best_raw_factors
print(f" [depth={_depth}] Accepted raw factors: {raw_factors}")
final_factors: List[int] = []
for f in raw_factors:
if f <= 1:
continue
if is_probable_prime(f):
final_factors.append(f)
else:
# Önce hızlı Pollard dene
d = pollard_rho(f, time_limit_sec=5.0)
if d and 1 < d < f:
final_factors.extend(
recursive_barantic_factor(d, max_workers=max_workers,
max_recursion=max_recursion, _depth=_depth + 1)
)
final_factors.extend(
recursive_barantic_factor(f // d, max_workers=max_workers,
max_recursion=max_recursion, _depth=_depth + 1)
)
else:
# Pollard başarısızsa, aynı recursive Barantic'i kullan
final_factors.extend(
recursive_barantic_factor(f, max_workers=max_workers,
max_recursion=max_recursion, _depth=_depth + 1)
)
final_factors.sort()
return final_factors
============================================================
Interactive Mode / Main
============================================================
def interactive_mode():
"""İnteraktif mod: kullanıcı N girer, recursive Barantic çalışır."""
print("=" * 70)
print("BARANTIC v0.3 - Recursive Parallel Smooth Fermat (P(n) = n // 2, stepped P)")
print(f"Default max_workers = {DEFAULT_MAX_WORKERS}, max_recursion = {MAX_RECURSION_DEPTH}")
print("=" * 70)
while True:
try:
N_input = input("\nN (enter boş bırak = çıkış): ").strip()
if not N_input:
break
N = int(N_input)
workers_input = input(f"Parallel workers [default={DEFAULT_MAX_WORKERS}]: ").strip()
if workers_input:
max_workers = int(workers_input)
else:
max_workers = DEFAULT_MAX_WORKERS
max_workers = max(1, min(max_workers, cpu_count()))
print(f"\n[+] Recursive Barantic factoring N with max_workers={max_workers} ...")
start = time.time()
factors = recursive_barantic_factor(N, max_workers=max_workers)
elapsed = time.time() - start
print("\n=== RESULT ===")
print(f"N = {N}")
print(f"Prime factors ({len(factors)}): {factors}")
prod = 1
for f in factors:
prod *= f
print(f"Product check: {prod == N} (product = {prod})")
print(f"Total time: {elapsed:.3f}s")
except KeyboardInterrupt:
print("\nÇıkılıyor...")
break
except Exception as e:
print(f"Hata: {e}")
continue
if name == "main":
import argparse
parser = argparse.ArgumentParser(description='Barantic v0.3 - Recursive Parallel Smooth Fermat (stepped P)')
parser.add_argument('-n', '--number', type=str, help='Number to factor')
parser.add_argument('-w', '--workers', type=int, default=DEFAULT_MAX_WORKERS,
help=f'Number of parallel workers (default={DEFAULT_MAX_WORKERS})')
parser.add_argument('--no-recursive', action='store_true',
help='Do NOT use recursive P(n)=n//2; run single Barantic call with manual P')
parser.add_argument('-p', '--primes', type=str,
help='P specification (e.g. "40", "1-40", "2,3,5,...") for non-recursive mode')
args = parser.parse_args()
if not args.number:
# Sayı verilmemişse interaktif moda geç
interactive_mode()
sys.exit(0)
N = int(args.number)
max_workers = max(1, min(args.workers, cpu_count()))
if args.no_recursive:
# Eski v0.2 davranışı: kullanıcı P_input veriyor
if not args.primes:
print("Error: --no-recursive modda -p/--primes parametresi zorunlu.")
sys.exit(1)
digits = len(str(N))
if digits <= 40:
timeout = 30.0
elif digits <= 60:
timeout = 60.0
elif digits <= 80:
timeout = 120.0
else:
timeout = 300.0
res = factor_with_enhanced_parallel_smooth_fermat(
N, args.primes,
max_workers=max_workers,
time_limit_sec=timeout,
max_steps=0,
rho_time=10.0,
ecm_time=10.0,
ecm_B1=100000,
ecm_curves=200
)
print("\nNon-recursive mode result:", res)
else:
# Varsayılan: recursive Barantic, P(n)=n//2 ve kademeli P
print(f"[MAIN] Recursive Barantic v0.3, N={N}, max_workers={max_workers}")
t0 = time.time()
factors = recursive_barantic_factor(N, max_workers=max_workers)
t1 = time.time()
print("\n=== FINAL RESULT (recursive) ===")
print(f"N = {N}")
print(f"Prime factors: {factors}")
prod = 1
for f in factors:
prod *= f
print(f"Product check: {prod == N} (product = {prod})")
print(f"Total time: {t1 - t0:.3f}s")
Top comments (1)
copy and paste to pycharm or etc. and see result.