Pollards kængurualgoritme

I beregningstalteori og beregningsmæssig algebra er Pollards kængurualgoritme (og også Pollards lambdaalgoritme , se afsnittet om titel nedenfor) en algoritme til løsning af det diskrete logaritmeproblem . Algoritmen blev foreslået i 1978 af talteoretikeren J. M. Pollard i samme papir [1] som hans bedre kendte ρ-algoritme til at løse det samme problem. Selvom Pollard beskriver anvendelsen af denne algoritme til det diskrete logaritmeproblem i en multiplikativ gruppe modulo a prime p , er det i virkeligheden en generel diskret logaritmealgoritme - den vil fungere på enhver cyklisk finit gruppe.

Algoritme

Lade være en endelig cyklisk gruppe af orden genereret af et element , og vi leder efter den diskrete logaritme af elementet med hensyn til basen . Med andre ord, vi leder efter , sådan at . Lambda-algoritmen giver os mulighed for at søge i en delmængde af . Vi kan søge efter det fulde sæt af mulige logaritmer ved at antage og , selvom ρ-algoritmen vil være mere effektiv i dette tilfælde. Vi går videre som følger: $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ælg et sæt heltal og definer en pseudo-tilfældig afbildning . $S$ $f:G\rightarrow S$

2. Vælg et heltal og beregn rækkefølgen af gruppeelementer i henhold til formlerne: $N$ $\{x_{0},x_{1},\ldots ,x_{N}\}$

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

3. Beregn

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

Læg mærke til det

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

4. Vi begynder at beregne den anden sekvens af gruppeelementer ved hjælp af formlerne ${\displaystyle \{y_{0},y_{1},\ldots \))$

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

og den tilsvarende sekvens af heltal ifølge formlen

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

Læg mærke til det

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

til

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

5. Stop computing , og når en af betingelserne er opfyldt $\{y_{i}\}$ $\{d_{i}\}$

A) for nogle . Hvis sekvenserne og "kolliderer" på denne måde, har vi:

y_{j}=x_{N}

j

\{x_i\}

\{y_{j}\}

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

så vi fandt, hvad vi ønskede. B) . Hvis dette sker, har algoritmen ikke kunnet finde . Et andet forsøg kan gøres ved at ændre sættet eller/og tilknytningen .

d_{i}>b-a+d

x

S

f

Sværhedsgrad

Pollard specificerede en tidskompleksitet for algoritmen , baseret på probabilistisk ræsonnement, som følger af antagelsen om, at f virker pseudo-tilfældigt. Bemærk, at i det tilfælde, hvor størrelsen af mængden { a , …, b } måles i bits , hvilket er sædvanligt i kompleksitetsteori , har mængden størrelseslog( b − a ), så den algoritmiske kompleksitet er lig med , som er en eksponent for problemstørrelsen. Af denne grund anses Pollards lambda-algoritme for at være en eksponentiel kompleksitetsalgoritme . For et eksempel på en tids-subeksponentiel algoritme, se Order calculus algoritme . ${\displaystyle {\scriptstyle O({\sqrt {ba))))))$ ${\scriptstyle O({\sqrt {ba)))=O(2^({\frac {1}{2}}\log(ba))))$

Titel

Algoritmen kendes under to navne.

Fornavnet er Pollards "kænguru"-algoritme . Navnet henviser til en analogi brugt i artiklen, hvor algoritmen blev foreslået. Artiklen forklarer algoritmen i forhold til at bruge en tam kænguru til at fange en vild . Som Pollard [2] forklarede , var denne analogi inspireret af et "charmerende" papir offentliggjort i samme nummer af Scientific American som udgivelsen af RSA Public Key Cryptosystem . Artikel [3] beskriver et eksperiment, hvor "energiomkostningerne ved at flytte en kænguru, målt i iltforbrug ved forskellige hastigheder, blev bestemt ved at placere en kænguru på et løbebånd ".

Det andet navn er Pollards lambda-algoritme . Meget lig navnet på Pollards anden algoritme for diskret logaritme, ρ-algoritmen , og dette navn skyldes algoritmens visualiseringslighed med det græske bogstav lambda ( ). Den korte linje i bogstavet lambda svarer til rækkefølgen . Følgelig svarer den lange linje til den sekvens , der "kolliderer med" den første sekvens (svarende til mødet mellem de korte og lange linjer i et bogstav). $\lambda$ $\{x_i\}$ $\{y_{i}\}$

Pollard foretrækker at bruge navnet "kænguru-algoritme" [4] for at undgå forveksling med nogle parallelle versioner af ρ-algoritmen, som også kaldes "lambda-algoritmer".

Se også

regnbuebord

Noter

↑ Pollard, 1978 .
↑ Pollard, 2000 , s. 437-447.
↑ Dawson, 1977 , s. 78-89.
↑ jmptidcott2 . Hentet 5. november 2016. Arkiveret fra originalen 17. august 2016. (ubestemt)

Litteratur

J. Pollard. Monte Carlo metoder til indeksberegning mod p // Mathematics of Computation. - 1978. - T. 32 .
J. Pollard. Kænguruer, monopol og diskrete logaritmer // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Kænguruer // Scientific American. - 1977. - S. 78-89 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme