Algoritmul Cangurului lui Pollard

În teoria numerelor computaționale și algebra computațională , algoritmul cangur al lui Pollard (și, de asemenea , algoritmul lambda al lui Pollard , vezi secțiunea Titlu de mai jos) este un algoritm pentru rezolvarea problemei logaritmului discret . Algoritmul a fost propus în 1978 de către teoreticianul numerelor J. M. Pollard în aceeași lucrare [1] ca și mai cunoscutul său algoritm ρ pentru rezolvarea aceleiași probleme. Deși Pollard descrie aplicarea acestui algoritm la problema logaritmului discret într-un grup multiplicativ modulo un prim p, este, de fapt, un algoritm general pentru logaritmul discret - va funcționa pe orice grup finit ciclic.

Algoritm

Fie un grup ciclic finit de ordin generat de un element și căutăm logaritmul discret al elementului față de bază . Cu alte cuvinte, căutăm , astfel încât . Algoritmul lambda ne permite să căutăm într-un subset de . Putem căuta întregul set de logaritmi posibili presupunând și , deși algoritmul ρ va fi mai eficient în acest caz. Procedăm astfel: $G$ $n$ $\alfa$ $X$ $\beta$ $\alfa$ $x\in Z_{n)$ $\alpha ^{x}=\beta$ $X$ $\{a,\ldots,b\}\subset Z_{n}$ $a=0$ $b=n-1$

1. Alegeți un set de numere întregi și definiți o mapare pseudo-aleatorie . $S$ $f:G\rightarrow S$

2. Alegeți un număr întreg și calculați succesiunea elementelor grupului conform formulelor: $N$ $\{x_{0},x_{1},\ldots ,x_{N}\}$

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

3. Calculați

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

observa asta

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

4. Începem să calculăm a doua secvență de elemente de grup folosind formulele ${\displaystyle \{y_{0},y_{1},\ldots \))$

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

și succesiunea corespunzătoare de numere întregi conform formulei

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

observa asta

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

pentru

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

5. Opriți calculul și când una dintre condiții este îndeplinită $\{y_{i}\}$ $\{d_{i}\}$

A) pentru unii . Dacă secvențele și „se ciocnesc” în acest fel, avem:

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}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}

asa ca am gasit ce ne-am dorit. B) . Dacă se întâmplă acest lucru, algoritmul nu a reușit să găsească . O altă încercare poate fi făcută prin schimbarea setului sau/și a maparii .

d_{i}>b-a+d

X

S

f

Dificultate

Pollard a specificat o complexitate temporală pentru algoritmul , bazată pe raționament probabilistic, care decurge din ipoteza că f acționează pseudo-aleatoriu. Rețineți că în cazul în care dimensiunea mulțimii { a , …, b } este măsurată în biți , ceea ce este uzual în teoria complexității , mulțimea are dimensiunea log( b − a ), deci complexitatea algoritmică este egală cu , care este un exponent al dimensiunii problemei. Din acest motiv, algoritmul lambda al lui Pollard este considerat a fi un algoritm de complexitate exponențială . Pentru un exemplu de algoritm subexponențial în timp, consultați Comandă algoritmul de calcul . ${\scriptstyle O({\sqrt {ba}})))$ ${\scriptstyle O({\sqrt {ba)})=O(2^({\frac {1}{2}}\log(ba))))$

Titlu

Algoritmul este cunoscut sub două nume.

Prenumele este algoritmul „cangur” al lui Pollard . Numele se referă la o analogie folosită în articolul în care a fost propus algoritmul. Articolul explică algoritmul în ceea ce privește utilizarea unui cangur îmblânzit pentru a captura unul sălbatic . După cum a explicat Pollard [2] , această analogie a fost inspirată de o lucrare „încântătoare” publicată în același număr al Scientific American ca și publicația RSA Public Key Cryptosystem . Articolul [3] descrie un experiment în care „costul energetic al mișcării unui cangur, măsurat în termeni de consum de oxigen la diferite viteze, a fost determinat prin plasarea unui cangur pe o bandă de alergare ”.

Al doilea nume este algoritmul lambda al lui Pollard . Foarte asemănător cu numele celuilalt algoritm al lui Pollard pentru logaritmul discret, algoritmul ρ , iar acest nume se datorează asemănării de vizualizare a algoritmului cu litera greacă lambda ( ). Linia scurtă a literei lambda corespunde secvenței . În consecință, linia lungă corespunde secvenței care „se ciocnește” cu prima secvență (similar cu întâlnirea liniilor scurte și lungi ale unei litere). $\lambda$ $\{x_i\}$ $\{y_{i}\}$

Pollard preferă să folosească denumirea de „algoritm cangur” [4] pentru a evita confuzia cu unele versiuni paralele ale algoritmului ρ, care sunt denumite și „algoritmi lambda”.

Vezi și

masa curcubeu

Note

↑ Pollard, 1978 .
↑ Pollard, 2000 , p. 437-447.
↑ Dawson, 1977 , p. 78-89.
↑ jmptidcott2 . Consultat la 5 noiembrie 2016. Arhivat din original la 17 august 2016. (nedefinit)

Literatură

J. Pollard. Metode Monte Carlo pentru calculul indicilor mod p // Matematica calculului. - 1978. - T. 32 .
J. Pollard. Canguri, monopol și logaritmi discreti // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Canguri // Scientific American. - 1977. - S. 78-89 .

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin