Pollard-féle ró algoritmus

Magyar

Kiejtés

• IPA: [ ˈpolːɒrtfeːlɛ ˈroː ˈɒlɡoritmuʃ]

Főnév

Pollard-féle ró algoritmus

1. (matematika, algoritmusok)

Pollard-féle Ró-algoritmus

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.

Algoritmus működése

1. Feltételek:
   • Adott egy $n$ szám, amelynek faktorizálását keressük.
   • Az algoritmus egy nem triviális osztót ($d$) próbál találni, ahol $1<d<n$.
2. Iteratív függvény:
   • Egy egyszerű iteratív függvényt használ, például:

$$f(x)=(x^{2}+c)\mod n$$ ahol $c$ egy tetszőleges konstans (általában 1).

1. Ciklusok és ismétlődések:
   • Az algoritmus a "teknős és nyúl" ciklusdetektálási módszert alkalmazza (Floyd algoritmusa).
   • Két iterátort használ:
   • Lassú iterátor ($x$): minden lépésben egy iterációt hajt végre.
   • Gyors iterátor ($y$): minden lépésben két iterációt hajt végre.
   • Ha az $x$ és $y$ iterátorok ugyanazt az értéket veszik fel, akkor egy ciklusba kerültek.
2. Nem triviális osztó keresése:
   • Ha egy ciklust talál, akkor kiszámítja a $\gcd(|x-y|,n)$-et, amely egy nem triviális osztót adhat.
3. Időbonyolultság:
   • Átlagosan $O({\sqrt {p}})$, ahol $p$ a legkisebb prímosztó.

Pszeudokód

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

Python implementáció

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

Példa

• Bemenet: $n=8051$
• Kimenet: Értelmezés sikertelen (formai hiba): {\displaystyle Talált\ osztó: 97}

C++ implementáció

#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;
}

Kimenet

Értelmezés sikertelen (formai hiba): {\displaystyle Talált\ osztó: 97}

Összegzés

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.

Fordítások

Tartalom

angol: Pollard's rho algorithm (en)

További információk

• Pollard-féle ró algoritmus - Értelmező szótár (MEK)
• Pollard-féle ró algoritmus - Etimológiai szótár (UMIL)
• Pollard-féle ró algoritmus - Szótár.net (hu-hu)
• Pollard-féle ró algoritmus - DeepL (hu-de)
• Pollard-féle ró algoritmus - Яндекс (hu-ru)
• Pollard-féle ró algoritmus - Google (hu-en)
• Pollard-féle ró algoritmus - Helyesírási szótár (MTA)
• Pollard-féle ró algoritmus - Wikidata
• Pollard-féle ró algoritmus - Wikipédia (magyar)