Pollardův algoritmus klokana

Ve výpočetní teorii čísel a výpočetní algebře je Pollardův klokaní algoritmus (a také Pollardův algoritmus lambda , viz nadpis níže) algoritmem pro řešení problému diskrétního logaritmu . Algoritmus navrhl v roce 1978 teoretik čísel J. M. Pollard ve stejném článku [1] jako jeho známější ρ-algoritmus pro řešení stejného problému. Ačkoli Pollard popisuje aplikaci tohoto algoritmu na problém diskrétního logaritmu v multiplikativní grupě modulo a prvočíslo p , ve skutečnosti se jedná o obecný algoritmus diskrétního logaritmu – bude fungovat na jakékoli cyklické konečné grupě.

Algoritmus

Nechť je konečná cyklická skupina řádu generovaná prvkem a hledáme diskrétní logaritmus prvku vzhledem k základně . Jinými slovy, hledáme takové, že . Algoritmus lambda nám umožňuje vyhledávat v nějaké podmnožině . Úplnou sadu možných logaritmů můžeme hledat za předpokladu a , ačkoliv ρ-algoritmus bude v tomto případě efektivnější. Postupujeme následovně: $G$ $n$ $\alpha$ $X$ $\beta$ $\alpha$ ${\displaystyle x\in Z_{n))$ $\alpha ^{x}=\beta$ $X$ $\{a,\ldots ,b\}\subset Z_{n}$ $a=0$ $b=n-1$

1. Vyberte sadu celých čísel a definujte pseudonáhodné zobrazení . $S$ $f:G\rightarrow S$

2. Vyberte celé číslo a vypočítejte posloupnost prvků skupiny podle vzorců: $N$ $\{x_{0},x_{1},\ldots ,x_{N}\}$

$x_{0}=\alpha ^{b}\,$
${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i)))))$ pro $i=0,1,\ldots ,N-1$

3. Vypočítejte

d=\sum _{i=0}^{N-1}f(x_{i})

všimněte si, že

x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.

4. Začneme počítat druhou sekvenci prvků skupiny pomocí vzorců ${\displaystyle \{y_{0},y_{1},\ldots \))$

$y_{0}=\beta \,$
${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i)))))$ pro $i=0,1,\ldots ,N-1$

a odpovídající posloupnost celých čísel podle vzorce

d_{n}=\sum _{i=0}^{n-1}f(y_{i})

všimněte si, že

y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}

pro

i=0,1,\ldots ,N-1

5. Zastavte výpočet a jakmile je splněna jedna z podmínek $\{y_{i}\}$ $\{d_{i}\}$

A) pro některé . Pokud se sekvence a "srazí" tímto způsobem, máme:

y_{j}=x_{N}

j

\{x_i\}

\{y_{j}\}

x_{N}=y_{j}\Šipka doprava \alpha ^{b+d}=\beta \alpha ^{d_{j))\Šipka doprava \beta =\alpha ^{b+d-d_{j }}{\pmod {n}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}

tak jsme našli, co jsme chtěli. B) . Pokud k tomu dojde, algoritmu se nepodařilo najít . Další pokus lze provést změnou sady nebo/a mapování .

d_{i}>b-a+d

X

S

F

Obtížnost

Pollard specifikoval časovou složitost pro algoritmus na základě pravděpodobnostního uvažování, které vyplývá z předpokladu, že f působí pseudonáhodně. Všimněte si, že v případě, kdy se velikost množiny { a , …, b } měří v bitech , což je obvyklé v teorii složitosti , má množina velikost log( b − a ), takže algoritmická složitost je rovna , což je exponent velikosti problému. Z tohoto důvodu je Pollardův lambda algoritmus považován za algoritmus exponenciální složitosti . Příklad časově-subexponenciálního algoritmu naleznete v tématu Algoritmus počtu objednávek . ${\displaystyle {\scriptstyle O({\sqrt {ba))))))$ ${\scriptstyle O({\sqrt {ba)))=O(2^({\frac {1}{2}}\log(ba))))$

Název

Algoritmus je znám pod dvěma názvy.

První název je Pollardův algoritmus „klokan“ . Název odkazuje na analogii použitou v článku, kde byl navržen algoritmus. Článek vysvětluje algoritmus z hlediska použití ochočeného klokana k odchytu divokého . Jak vysvětlil Pollard [2] , tato analogie byla inspirována „okouzlujícím“ článkem publikovaným ve stejném čísle Scientific American jako publikace RSA Public Key Cryptosystem . Článek [3] popisuje experiment, ve kterém „náklady na energii na pohyb klokana, měřené jako spotřeba kyslíku při různých rychlostech, byly určeny umístěním klokana na běžící pás “.

Druhý název je Pollardův lambda algoritmus . Velmi podobný jménu jiného Pollardova algoritmu pro diskrétní logaritmus, ρ-algoritmu , a tento název je způsoben vizualizační podobností algoritmu s řeckým písmenem lambda ( ). Krátký řádek písmene lambda odpovídá sekvenci . Dlouhý řádek tedy odpovídá posloupnosti , která "koliduje" s první posloupností (podobně jako setkání krátkých a dlouhých řádků písmene). $\lambda$ $\{x_i\}$ $\{y_{i}\}$

Pollard upřednostňuje použití názvu „klokaní algoritmus“ [4] , aby se vyhnul záměně s některými paralelními verzemi ρ-algoritmu, které se také nazývají „algoritmy lambda“.

Viz také

duhový stůl

Poznámky

↑ Pollard, 1978 .
↑ Pollard, 2000 , str. 437-447.
↑ Dawson, 1977 , s. 78-89.
↑ jmptidcott2 . Získáno 5. listopadu 2016. Archivováno z originálu 17. srpna 2016. (neurčitý)

Literatura

J. Pollard. Metody Monte Carlo pro výpočet indexu mod p // Matematika výpočtu. - 1978. - T. 32 .
J. Pollard. Klokani, monopoly a diskrétní logaritmy // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Klokani // Scientific American. - 1977. - S. 78-89 .

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin