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,\dots ,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,\dots ,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,\dots ,x_N)$ als: $x_0=g^b$ en $x_{i+1}=x_i\cdot g^{f(x_i)}$ voor $i=0,1,\dots ,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 \dots \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,\dots ,y_N)$ als: $y_0=h,y_{i+1}=y_i\cdot g^{f(y_i)}$ voor $i=0,1,\dots ,N-1$
Bereken tegelijkertijd de rij $(d_0,d_1,\dots$ 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 \dots \cdot g^{f(y_i)}=h\cdot g^{d_i}$ voor $i=0,1,\dots ,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\iff g^{b+d}=h\cdot g^{d_j}\iff h=g^{b+d-d_j}$ waaruit de gezochte $n\equiv b+d-d_j(\mathrm{mod}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