Algoritmus Pollards rho - Pollards rho algorithm - Wikipedia

Pollardův rho algoritmus je algoritmus pro celočíselná faktorizace. To bylo vynalezeno John Pollard v roce 1975.^[1] Využívá jen malé množství prostoru a jeho očekávaná doba chodu je úměrná druhé odmocnině velikosti nejmenšího hlavní faktor z složené číslo je faktorizovaný.

Základní myšlenky

Předpokládejme, že musíme rozložit číslo ${ displaystyle n = pq}$, kde ${ displaystyle p}$ je netriviální faktor. Polynomiální modulo ${ displaystyle n}$, volala ${ displaystyle g (x)}$ (např., ${ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}$), se používá ke generování a pseudonáhodná posloupnost: Je vybrána počáteční hodnota, řekněme 2, a sekvence pokračuje jako ${ displaystyle x_ {1} = g (2)}$, ${ displaystyle x_ {2} = g (g (2))}$, ${ displaystyle x_ {3} = g (g (g (2)))}$Sekvence souvisí s jinou sekvencí ${ displaystyle {x_ {k} { bmod {p}} }}$. Od té doby ${ displaystyle p}$ není předem známa, nelze tuto sekvenci v algoritmu explicitně vypočítat. Přesto v tom spočívá základní myšlenka algoritmu.

Protože počet možných hodnot pro tyto sekvence je konečný, oba ${ displaystyle {x_ {k} }}$ sekvence, což je mod ${ displaystyle n}$, a ${ displaystyle {x_ {k} { bmod {p}} }}$ posloupnost se nakonec bude opakovat, i když tu druhou neznáme. Předpokládejme, že se sekvence chovají jako náhodná čísla. V důsledku narozeninový paradox, počet ${ displaystyle x_ {k}}$ Před opakováním se očekává, že bude ${ displaystyle O ({ sqrt {N}})}$, kde ${ displaystyle N}$ je počet možných hodnot. Takže sekvence ${ displaystyle {x_ {k} { bmod {p}} }}$ bude pravděpodobně opakovat mnohem dříve než sekvence ${ displaystyle {x_ {k} }}$. Jakmile má sekvence opakovanou hodnotu, bude sekvence cyklovat, protože každá hodnota závisí pouze na té před ní. Tato struktura případného cyklování vede ke vzniku názvu „Algoritmus Rho“, vzhledem k podobnosti tvaru řeckého znaku ρ, když hodnoty ${ displaystyle x_ {1} { bmod {p}}}$, ${ displaystyle x_ {2} { bmod {p}}}$, atd. jsou reprezentovány jako uzly v a řízený graf.

Cyklický diagram připomínající řecké písmeno ρ

To zjistí Floydův algoritmus pro vyhledávání cyklů: dva uzly ${ displaystyle i}$ a ${ displaystyle j}$ (tj., ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$) jsou drženi. V každém kroku se jeden přesune do dalšího uzlu v sekvenci a druhý se posune vpřed o dva uzly. Poté se zkontroluje, zda ${ displaystyle gcd (x_ {i} -x_ {j}, n) neq 1}$. Pokud to není 1, znamená to, že v opakování je opakování ${ displaystyle {x_ {k} { bmod {p}} }}$ sekvence (tj. ${ displaystyle x_ {i} { bmod {p}} = x_ {j} { bmod {p}})}$. To funguje, protože pokud ${ displaystyle x_ {i}}$ je stejné jako ${ displaystyle x_ {j}}$, rozdíl mezi ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ je nutně násobkem ${ displaystyle p}$. I když se to vždy stane nakonec, výsledkem Největší společný dělitel (GCD) je dělitelem ${ displaystyle n}$ jiné než 1. To může být ${ displaystyle n}$ sám, protože tyto dvě sekvence se mohou opakovat současně. V tomto (neobvyklém) případě algoritmus selže a lze jej opakovat s jiným parametrem.

Algoritmus

Algoritmus bere jako své vstupy n, celé číslo, které má být zohledněno; a ${ displaystyle g (x)}$, polynom v X vypočítané modulo n. V původním algoritmu ${ displaystyle g (x) = (x ^ {2} -1) { bmod {n}}}$, ale v dnešní době je běžnější používat ${ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}$. Výstup je buď netriviální faktor nnebo selhání. Provádí následující kroky:^[2]

    x ← 2 y ← 2 d ← 1 zatímco d = 1: x ← g (x) y ← g (g (y)) d ← gcd (| x - y |, n) -li d = n: selhání návratu    jiný:        vrátit se d

Tady X a y odpovídá ${ displaystyle x_ {i}}$ a ${ displaystyle x_ {j}}$ v části o základní myšlence. Všimněte si, že tento algoritmus nemusí najít netriviální faktor, i když n je složený. V takovém případě lze metodu vyzkoušet znovu pomocí jiné počáteční hodnoty než 2 nebo jiné ${ displaystyle g (x)}$.

Příklad faktorizace

Nechat ${ displaystyle n = 8051}$ a ${ displaystyle g (x) = (x ^ {2} +1) { bmod {8}} 051}$.

97 je netriviální faktor 8051. Počáteční hodnoty jiné než X = y = 2 může dát kofaktor (83) místo 97. Jedna další iterace je uvedena výše, aby bylo jasné, že y se pohybuje dvakrát rychleji než X. Všimněte si, že i po opakování se GCD může vrátit na 1.

Varianty

V roce 1980 Richard Brent zveřejnil rychlejší variantu algoritmu rho. Použil stejné základní myšlenky jako Pollard, ale jinou metodu detekce cyklu a nahradil ji Floydův algoritmus pro vyhledávání cyklů se souvisejícími Brentova metoda hledání cyklu.^[3]

Další vylepšení provedli Pollard a Brent. Pozorovali, že pokud ${ displaystyle gcd (a, n)> 1}$, pak také ${ displaystyle gcd (ab, n)> 1}$ pro jakékoli kladné celé číslo ${ displaystyle b}$. Zejména místo výpočtů ${ displaystyle gcd (| x-y |, n)}$ na každém kroku to stačí definovat ${ displaystyle z}$ jako produkt 100 po sobě jdoucích ${ displaystyle | x-y |}$ termíny modulo ${ displaystyle n}$a poté spočítat jeden ${ displaystyle gcd (z, n)}$. Hlavní zrychlení má za následek 100 gcd kroky jsou nahrazeny 99 multiplikacemi modulo ${ displaystyle n}$ a jeden gcd. Občas to může způsobit selhání algoritmu zavedením opakovaného faktoru, například když ${ displaystyle n}$ je čtverec. Potom však stačí vrátit se k předchozímu gcd termín, kde ${ displaystyle gcd (z, n) = 1}$a odtud použijte běžný algoritmus ρ.

aplikace

Algoritmus je velmi rychlý pro čísla s malými faktory, ale pomalejší v případech, kdy jsou všechny faktory velké. Nejpozoruhodnějším úspěchem algoritmu ρ byla faktorizace Číslo Fermata F₈ = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321 ^[4]. Algoritmus ρ byl dobrou volbou F₈ protože hlavní faktor p = 1238926361552897 je mnohem menší než druhý faktor. Faktorizace trvala 2 hodiny na a UNIVAC 1100/42.^[4]

Příklad n = 10403 = 101 · 103

Zde představíme další variantu, kde se počítá pouze jedna sekvence, a gcd se počítá uvnitř smyčky, která detekuje cyklus.

Ukázka kódu C.

Následující ukázka kódu najde faktor 101 10403 s počáteční hodnotou X = 2.

#zahrnout <stdio.h>#zahrnout <stdlib.h>int gcd(int A, int b) {    int zbytek;    zatímco (b != 0) {        zbytek = A % b;        A = b;        b = zbytek;    }    vrátit se A;}int hlavní (int argc, char *argv[]) {    int číslo = 10403, smyčka = 1, počet;    int x_fixed = 2, X = 2, velikost = 2, faktor;    dělat {        printf("---- smyčka% 4i ---- n", smyčka);        počet = velikost;        dělat {            X = (X * X + 1) % číslo;            faktor = gcd(břišní svaly(X - x_fixed), číslo);            printf("count =% 4i x =% 6i faktor =% i n", velikost - počet + 1, X, faktor);        } zatímco (--počet && (faktor == 1));        velikost *= 2;        x_fixed = X;        smyčka = smyčka + 1;    } zatímco (faktor == 1);    printf("faktor je% i n", faktor);    vrátit se faktor == číslo ? EXIT_FAILURE : EXIT_SUCCESS;}

Výše uvedený kód bude zobrazovat průběh algoritmu i mezilehlé hodnoty. Konečný výstupní řádek bude „faktor je 101“. Kód bude fungovat pouze pro malé testovací hodnoty, protože k přetečení dojde v celočíselných datových typech během čtverce x.

Ukázka kódu Pythonu

z itertools import početz matematika import gcdčíslo, X = 10403, 2pro cyklus v počet(1):    y = X    pro i v rozsah(2 ** cyklus):        X = (X * X + 1) % číslo        faktor = gcd(X - y, číslo)        -li faktor > 1:            tisk(„faktor je“, faktor)            výstup()

Výsledky

V následující tabulce obsahuje třetí a čtvrtý sloupec tajné informace, které osoba, která se pokouší vytvořit faktor, nezná pq = 10403. Jsou zahrnuty, aby ukázaly, jak algoritmus funguje. Pokud začneme s X = 2 a podle algoritmu dostaneme následující čísla:

${ displaystyle x}$	${ displaystyle x_ {opravený}}$	${ displaystyle x { bmod {1}} 01}$	${ displaystyle x_ {fixed} { bmod {1}} 01}$	krok
2	2	2	2	0
5	2	5	2	1
26	2	26	2	2
677	26	71	26	3
598	26	93	26	4
3903	26	65	26	5
3418	26	85	26	6
156	3418	55	85	7
3531	3418	97	85	8
5168	3418	17	85	9
3724	3418	88	85	10
978	3418	69	85	11
9812	3418	15	85	12
5983	3418	24	85	13
9970	3418	72	85	14
236	9970	34	72	15
3682	9970	46	72	16
2016	9970	97	72	17
7087	9970	17	72	18
10289	9970	88	72	19
2594	9970	69	72	20
8499	9970	15	72	21
4973	9970	24	72	22
2799	9970	72	72	23

První opakovací modulo 101 je 97, ke kterému dochází v kroku 17. Opakování je detekováno až v kroku 23, kdy ${ displaystyle x equiv x_ {fixed} { pmod {101}}}$. To způsobuje ${ displaystyle gcd (x-x_ {fixed}, n) = gcd (2799-9970, n)}$ být ${ displaystyle p = 101}$a je nalezen faktor.

Složitost

Pokud je pseudonáhodné číslo ${ displaystyle x = g (x)}$ vyskytující se v algoritmu Pollard ρ byly skutečné náhodné číslo, z toho by vyplývalo, že úspěchu by bylo dosaženo polovinu času, Paradox k narozeninám v ${ displaystyle O ({ sqrt {p}}) leq O (n ^ {1/4})}$ iterace. Předpokládá se, že stejná analýza platí také pro skutečný algoritmus rho, ale toto je heuristické tvrzení a důsledná analýza algoritmu zůstává otevřená.^[5]

Viz také

• Pollardův rho algoritmus pro logaritmy
• Pollardův klokanový algoritmus

Reference

Další čtení

• Katz, Jonathan; Lindell, Yehuda (2007). „Kapitola 8“. Úvod do moderní kryptografie. CRC Press.
• Samuel S. Wagstaff, Jr. (2013). Radost z faktoringu. Providence, RI: American Mathematical Society. str. 135–138. ISBN  978-1-4704-1048-3.

externí odkazy

• Komplexní článek o Pollardově Rho algoritmu zaměřený na publikum na úvodní úrovni
• Weisstein, Eric W. „Metoda faktorizace Pollard rho“. MathWorld.
• Implementace Java
• O společnosti Pollard rho