Pollard-féle ró algoritmus

• IPA:

Pollard-féle ró algoritmus

1. (matematika, algoritmusok)

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.

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

$${\displaystyle f(x)=(x^{2}+c)\mod n}$$ ahol ${\displaystyle 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 (${\displaystyle x}$): minden lépésben egy iterációt hajt végre.
   • Gyors iterátor (${\displaystyle y}$): minden lépésben két iterációt hajt végre.
   • Ha az ${\displaystyle x}$ és ${\displaystyle 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 ${\displaystyle \gcd(|x-y|,n)}$-et, amely egy nem triviális osztót adhat.
3. Időbonyolultság:
   • Átlagosan ${\displaystyle O({\sqrt {p}})}$, ahol ${\displaystyle p}$ a legkisebb prímosztó.

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

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

#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.

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