Pollard kenguru algoritmusa

A számítási számelméletben és a számítási algebrában a Pollard-féle kenguru-algoritmus (és a Pollard-féle lambda-algoritmus is , lásd a címet alább) a diszkrét logaritmus -probléma megoldására szolgáló algoritmus . Az algoritmust 1978-ban J. M. Pollard javasolta ugyanabban a cikkben [1] , mint az ő ismertebb ρ-algoritmusát ugyanazon probléma megoldására. Bár Pollard leírja ennek az algoritmusnak az alkalmazását a diszkrét logaritmus-problémára egy modulo a pr prím multiplikatív csoportban , valójában ez egy általános diszkrét logaritmus-algoritmus – minden ciklikus véges csoporton működik.

Algoritmus

Legyen egy elem által generált véges ciklikus rendű csoport , és keressük az elem diszkrét logaritmusát az alaphoz képest . Más szóval, olyat keresünk , hogy . A lambda-algoritmus lehetővé teszi, hogy a -nak valamely részhalmazában keressünk . Megkereshetjük a lehetséges logaritmusok teljes halmazát és feltételezésével , bár a ρ-algoritmus ebben az esetben hatékonyabb lesz. A következőképpen járunk el: $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. Válassza ki az egész számok halmazát, és határozzon meg egy pszeudo-véletlen leképezést . $S$ $f:G\rightarrow S$

2. Válasszon egy egész számot , és számítsa ki a csoportelemek sorrendjét a képletek alapján: $N$ $\{x_{0},x_{1},\ldots ,x_{N}\}$

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

3. Számítsa ki

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

vegye észre, az

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

4. A képletek segítségével elkezdjük kiszámítani a csoportelemek második sorozatát ${\displaystyle \{y_{0},y_{1},\ldots \))$

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

és a megfelelő egész számsorozat a képlet szerint

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

vegye észre, az

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

számára

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

5. Ha az egyik feltétel teljesül, állítsa le a számítást $\{y_{i}\}$ $\{d_{i}\}$

A) egyesek számára . Ha a sorozatok és a szekvenciák ilyen módon "ütköznek", akkor:

y_{j}=x_{N}

j

\{x_i\}

\{y_{j}\}

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

így megtaláltuk, amit akartunk. B) . Ha ez megtörténik, az algoritmus nem találta meg a . Egy másik kísérlet a halmaz és/vagy a leképezés megváltoztatásával tehető .

d_{i}>b-a+d

x

S

f

Nehézség

Pollard a valószínűségi okoskodáson alapuló időbonyolultságot adott meg az algoritmus számára , ami abból a feltevésből következik, hogy f álvéletlenszerűen működik. Megjegyzendő, hogy abban az esetben, ha az { a , …, b } halmaz méretét bitben mérjük , ami a komplexitáselméletben szokásos , akkor a halmaz log( b − a ) mérettel rendelkezik, így az algoritmikus komplexitás egyenlő : amely a probléma méretének kitevője . Emiatt a Pollard-féle lambda-algoritmus egy exponenciális összetettségű algoritmusnak tekinthető . Egy idő-szubexponenciális algoritmus példáját a Számítási algoritmus sorrendje című témakörben találja . ${\displaystyle {\scriptstyle O({\sqrt {ba))))))$ ${\scriptstyle O({\sqrt {ba)))=O(2^({\frac {1}{2}}\log(ba))))$

Cím

Az algoritmust két néven ismerjük.

Az első név Pollard "kenguru" algoritmusa . A név a cikkben használt analógiára utal, ahol az algoritmust javasolták. A cikk elmagyarázza az algoritmust egy szelíd kenguru használatával egy vad kenguru elfogására . Amint Pollard [2] kifejtette , ezt az analógiát egy "bájos" cikk ihlette, amely a Scientific American ugyanabban a számában jelent meg, mint az RSA nyilvános kulcsú kriptorendszer kiadása . A [3] cikk egy kísérletet ír le, amelyben "egy kenguru mozgatásának energiaköltségét, amelyet az oxigénfogyasztásban mértek különböző sebességeknél, úgy határozták meg, hogy egy kengurut egy futópadra helyeztek " .

A második név Pollard lambda algoritmusa . Nagyon hasonlít Pollard másik diszkrét logaritmus algoritmusának nevéhez, a ρ-algoritmushoz , és ez a név az algoritmus vizualizációs hasonlóságának köszönhető a görög lambda ( ) betűhöz. A lambda betű rövid sora a sorozatnak felel meg . Ennek megfelelően a hosszú sor annak a sorozatnak felel meg, amely "ütközik" az első sorozattal (hasonlóan egy betű rövid és hosszú sorainak találkozásához). $\lambda$ $\{x_i\}$ $\{y_{i}\}$

Pollard szívesebben használja a "kenguru algoritmus" [4] nevet , hogy elkerülje a ρ-algoritmus néhány párhuzamos változatával való összetévesztést, amelyeket "lambda-algoritmusnak" is neveznek.

Lásd még

szivárvány asztal

Jegyzetek

↑ Pollard, 1978 .
↑ Pollard, 2000 , p. 437-447.
↑ Dawson, 1977 , p. 78-89.
↑ jmptidcott2 . Letöltve: 2016. november 5. Az eredetiből archiválva : 2016. augusztus 17.. (határozatlan)

Irodalom

J. Pollard. Monte Carlo módszerek indexszámításhoz mod p // Számítási matematika. - 1978. - T. 32 .
J. Pollard. Kenguruk, monopólium és diszkrét logaritmusok // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Kenguruk // Scientific American. - 1977. - S. 78-89 .

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus