A Pollard-féle Ró-algoritmus egy hatékony probabilisztikus algoritmus, amelyet nagy számok faktorizálására használnak. Az algoritmus az ismétlődéseket és ciklusokat használja ki egy determinisztikus iteráció során, hogy találjon egy nem triviális osztót.
ahol egy tetszőleges konstans (általában 1).
function PollardRho(n):
ha n páros, térj vissza 2
x = 2, y = 2, d = 1
f(x) = (x^2 + 1) mod n
amíg d == 1:
x = f(x)
y = f(f(y))
d = gcd(|x - y|, n)
ha d == n, térj vissza "Nem sikerült osztót találni"
különben térj vissza d
import math
import random
def pollard_rho(n):
if n % 2 == 0:
return 2
# Iteratív függvény: f(x) = (x^2 + c) mod n
def f(x):
return (x'''2 + 1) % n
x = random.randint(2, n - 1)
y = x
d = 1
while d == 1:
x = f(x) # Lassú iterátor
y = f(f(y)) # Gyors iterátor
d = math.gcd(abs(x - y), n)
if d == n:
return None # Nem talált nem triviális osztót
return d
# Példa használat
n = 8051 # Faktorizálandó szám
oszto = pollard_rho(n)
if oszto:
print(f"Talált osztó: {oszto}")
else:
print("Nem sikerült osztót találni.")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;
// Iteratív függvény
long long f(long long x, long long n) {
return (x * x + 1) % n;
}
// Pollard-féle Ró-algoritmus
long long pollard_rho(long long n) {
if (n % 2 == 0) return 2;
long long x = rand() % (n - 2) + 2;
long long y = x;
long long d = 1;
while (d == 1) {
x = f(x, n); // Lassú iterátor
y = f(f(y, n), n); // Gyors iterátor
d = __gcd(abs(x - y), n);
}
if (d == n) return -1; // Nem talált osztót
return d;
}
int main() {
srand(time(0));
long long n = 8051; // Faktorizálandó szám
long long oszto = pollard_rho(n);
if (oszto != -1) {
cout << "Talált osztó: " << oszto << endl;
} else {
cout << "Nem sikerült osztót találni." << endl;
}
return 0;
}
Értelmezés sikertelen (formai hiba): {\displaystyle Talált\ osztó: 97}
A Pollard-féle Ró-algoritmus egy hatékony, probabilisztikus módszer nagy számok faktorizálására. Bár nem garantált, hogy minden esetben talál osztót, az algoritmus jól működik a legtöbb gyakorlati esetben. Használata gyakori titkosítási rendszerek gyengeségeinek kihasználására, például az RSA kulcsok faktorizálására.