Pollards kängurualgoritm

I beräkningstalteori och beräkningsalgebra är Pollards kängurualgoritm (och även Pollards lambdaalgoritm , se rubrikavsnittet nedan) en algoritm för att lösa det diskreta logaritmproblemet . Algoritmen föreslogs 1978 av nummerteoretikern J. M. Pollard i samma artikel [1] som hans mer kända ρ-algoritm för att lösa samma problem. Även om Pollard beskriver tillämpningen av denna algoritm på det diskreta logaritmproblemet i en multiplikativ grupp modulo a prime p , är det i själva verket en allmän diskret logaritmalgoritm – den kommer att fungera på vilken cyklisk finit grupp som helst.

Algoritm

Låta vara en ändlig cyklisk grupp av ordning som genereras av ett element , och vi letar efter den diskreta logaritmen av elementet med avseende på basen . Med andra ord letar vi efter , sådan att . Lambdaalgoritmen låter oss söka i någon delmängd av . Vi kan söka efter hela uppsättningen möjliga logaritmer genom att anta och , även om ρ-algoritmen kommer att vara mer effektiv i detta fall. Vi går tillväga enligt följande: $G$ $n$ $\alfa$ $x$ $\beta$ $\alfa$ ${\displaystyle x\in Z_{n))$ $\alpha ^{x}=\beta$ $x$ $\{a,\ldots ,b\}\subset Z_{n}$ $a=0$ $b=n-1$

1. Välj en uppsättning heltal och definiera en pseudo-slumpmässig mappning . $S$ $f:G\rightarrow S$

2. Välj ett heltal och beräkna sekvensen av gruppelement enligt formlerna: $N$ $\{x_{0},x_{1},\ldots ,x_{N}\}$

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

3. Beräkna

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

Lägg märke till att

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

4. Vi börjar beräkna den andra sekvensen av gruppelement med hjälp av formlerna ${\displaystyle \{y_{0},y_{1},\ldots \))$

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

och motsvarande sekvens av heltal enligt formeln

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

Lägg märke till att

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

för

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

5. Sluta beräkna och när något av villkoren är uppfyllt $\{y_{i}\}$ $\{d_{i}\}$

A) för vissa . Om sekvenserna och "krockar" på detta sätt har vi:

y_{j}=x_{N}

j

\{x_i\}

\{y_{j}\}

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

så vi hittade vad vi ville ha. B) . Om detta händer har algoritmen inte lyckats hitta . Ett annat försök kan göras genom att ändra uppsättningen eller/och mappningen .

d_{i}>b-a+d

x

S

f

Svårighet

Pollard specificerade en tidskomplexitet för algoritmen , baserat på probabilistiska resonemang, som följer av antagandet att f fungerar pseudo-slumpmässigt. Observera att i fallet när storleken på mängden { a , …, b } mäts i bitar , vilket är vanligt inom komplexitetsteorin , har mängden storleksloggen( b − a ), så den algoritmiska komplexiteten är lika med , vilket är en exponent för problemets storlek. Av denna anledning anses Pollards lambdaalgoritm vara en exponentiell komplexitetsalgoritm . För ett exempel på en tidssubexponentiell algoritm, se Ordningskalkylalgoritm . ${\displaystyle {\scriptstyle O({\sqrt {ba))))))$ ${\scriptstyle O({\sqrt {ba)))=O(2^({\frac {1}{2}}\log(ba))))$

Titel

Algoritmen är känd under två namn.

Förnamnet är Pollards "känguru"-algoritm . Namnet hänvisar till en analogi som används i artikeln där algoritmen föreslogs. Artikeln förklarar algoritmen i termer av att använda en tam känguru för att fånga en vild . Som Pollard [2] förklarade , var denna analogi inspirerad av ett "charmigt" dokument som publicerades i samma nummer av Scientific American som publiceringen av RSA Public Key Cryptosystem . Artikel [3] beskriver ett experiment där "energikostnaden för att flytta en känguru, mätt i termer av syreförbrukning vid olika hastigheter, bestämdes genom att placera en känguru på ett löpband ".

Det andra namnet är Pollards lambdaalgoritm . Mycket likt namnet på Pollards andra algoritm för diskret logaritm, ρ-algoritmen , och detta namn beror på algoritmens visualiseringslikhet med den grekiska bokstaven lambda ( ). Den korta raden i bokstaven lambda motsvarar sekvensen . Följaktligen motsvarar den långa raden den sekvens som "krockar med" den första sekvensen (liknande mötet mellan de korta och långa linjerna i en bokstav). $\lambda$ $\{x_i\}$ $\{y_{i}\}$

Pollard föredrar att använda namnet "kängurualgoritm" [4] för att undvika förväxling med vissa parallella versioner av ρ-algoritmen, som också kallas "lambdaalgoritmer".

Se även

regnbågsbord

Anteckningar

↑ Pollard, 1978 .
↑ Pollard, 2000 , sid. 437-447.
↑ Dawson, 1977 , sid. 78-89.
↑ jmptidcott2 . Hämtad 5 november 2016. Arkiverad från originalet 17 augusti 2016. (obestämd)

Litteratur

J. Pollard. Monte Carlo metoder för indexberäkning mod p // Mathematics of Computation. - 1978. - T. 32 .
J. Pollard. Känguruer, monopol och diskreta logaritmer // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Känguruer // Scientific American. - 1977. - S. 78-89 .

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm