Pollard-féle ró algoritmus

Üdvözlöm, Ön a Pollard-féle ró algoritmus szó jelentését keresi. A DICTIOUS-ban nem csak a Pollard-féle ró algoritmus szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a Pollard-féle ró algoritmus szót egyes és többes számban mondani. Minden, amit a Pollard-féle ró algoritmus szóról tudni kell, itt található. A Pollard-féle ró algoritmus szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. APollard-féle ró algoritmus és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Kiejtés

  • IPA:

Főnév

Pollard-féle 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 szám, amelynek faktorizálását keressük.
    • Az algoritmus egy nem triviális osztót () próbál találni, ahol .
  2. Iteratív függvény:
    • Egy egyszerű iteratív függvényt használ, például:

ahol 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 (): minden lépésben egy iterációt hajt végre.
    • Gyors iterátor (): minden lépésben két iterációt hajt végre.
    • Ha az és 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 -et, amely egy nem triviális osztót adhat.
  3. Időbonyolultság:
    • Átlagosan , ahol 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:
  • 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