Pollards lambda-algoritme

Pollards lambda-algoritme, ook bekend onder de naam Pollards kangoeroe-algoritme, is een algoritme om de discrete logaritme te vinden. De Britse wiskundige John Pollard beschreef deze methode in hetzelfde artikel als waarin hij Pollards rho-algoritme voor logaritmen beschreef.

Pollards lambda-algoritme is bruikbaar om de discrete logaritme te bepalen, als men weet dat deze tot een beperkt aantal waarden $\{a,\ldots ,b\}$ behoort.

Door $a=0$ en $b=p-1$ te stellen is het mogelijk om het Pollard lambda-algoritme voor algemene $n$ te gebruiken, maar Pollards lambda-algoritme gaat veel sneller als $\{a,\ldots ,b\}$ een relatief klein aantal waarden bevat.

Het algoritme

Kies een verzameling S met gehele getallen en definier een functie f(x) die de groep G afbeeldt op deze verzameling S.
Kies vervolgens een geheel getal N en bereken een rij groepselementen $(x_{0},x_{1},\ldots ,x_{N})$ als: $x_{0}=g^{b}$ en $x_{i+1}=x_{i}\cdot g^{f(x_{i})}$ voor $i=0,1,\ldots ,N-1$.
Berekenen daarna de som van alle afzonderlijke $f(x_{i})$: $d=\sum _{i=0}^{N-1}f(x_{i})$
Er geldt nu dus:

$x_{N}=x_{0}\cdot g^{f(x_{0})}\cdot g^{f(x_{1})}\cdot \ldots \cdot g^{f(x_{N-1})}=x_{0}\cdot g^{d}=g^{b}\cdot g^{d}=g^{b+d}$

Berekenen nu een tweede reeks groepselementen $(y_{0},y_{1},\ldots ,y_{N})$ als: $y_{0}=h,y_{i+1}=y_{i}\cdot g^{f(y_{i})}$ voor $i=0,1,\ldots ,N-1$
Bereken tegelijkertijd de rij $(d_{0},d_{1},\ldots$ waarbij $d_{k}=\sum _{i=0}^{k-1}f(y_{i})$
Dan geldt: $y_{i}=y_{0}\cdot g^{f(y_{0})}\cdot g^{f(y_{1})}\cdot \ldots \cdot g^{f(y_{i})}=h\cdot g^{d_{i}}$ voor $i=0,1,\ldots ,N-1$
Ga door met het berekenen van nieuwe termen $y_{i}$ en $d_{i}$ totdat een van de volgende twee situaties optreedt:

i) $y_{j}=x_{N}$ voor bepaalde $j$.

Dan geldt: $x_{N}=y_{j}\Leftrightarrow g^{b+d}=h\cdot g^{d_{j}}\Leftrightarrow h=g^{b+d-d_{j}}$ waaruit de gezochte $n\equiv b+d-d_{j}{\pmod {p}}$ gevonden kan worden.

ii) $d_{i}=b-a+d$

Wanneer dit gebeurt, kan $n$ zo niet worden bepaald.

We kunnen de verzameling S en/of de functie f(x) veranderen en opnieuw de verschillende stappen van het algoritme doorlopen.

Zie ook

• Baby-steps giant-steps algoritme
• Indexcalculusalgoritme
• Pohlig-Hellman algoritme
• Pollards rho-algoritme

Referenties

• J. M. Pollard, Monte Carlo methods for index computation mod p. Mathematics of Computation, Volume 32, Issue 143 (jul.1978), 918-924.
• M. Pollard, Kangaroos, Monopoly and Discrete Logarithms. Journal of Cryptology, Volume 13, pp 437–447, 2000