New FASTEST RSA GRADE Prime Factorisition PHYTON CODE-10ms for 74digit

ozgur kiyafet — Tue, 18 Nov 2025 00:07:50 +0000

-- 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")

DEV Community: ozgur kiyafet

New FASTEST RSA GRADE Prime Factorisition PHYTON CODE-10ms for 74digit

-- coding: utf-8 --

Python 3.11+ integer string limitini kaldır (büyük sayıları rahat yazdırabilmek için)

============================================================

Sabitler

============================================================

============================================================

Temel Matematik Fonksiyonları

============================================================

============================================================

Adım Sayısı Hesabı (Genişletilmiş Limitler)

============================================================

============================================================

Smooth Fermat Temel Fonksiyonları

============================================================

============================================================

Paralel Şapka: Worker ve Parallel Wrapper

============================================================

============================================================

P Hesabı (Safe P Calculation)

============================================================

============================================================

Ana Wrapper (tek çağrıda factoring), recursive olmadan

============================================================

============================================================

YENİ: Recursive Barantic (P(n) = n // 2, kademeli P)

============================================================

============================================================

Interactive Mode / Main

============================================================