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,…,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,…,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 (x0,x1,…,xN) als: x0=gb en xi+1=xi⋅gf(xi) voor i=0,1,…,N−1.
Berekenen daarna de som van alle afzonderlijke f(xi): d=∑i=0N−1f(xi)
Er geldt nu dus:

xN=x0⋅gf(x0)⋅gf(x1)⋅…⋅gf(xN−1)=x0⋅gd=gb⋅gd=gb+d

Berekenen nu een tweede reeks groepselementen (y0,y1,…,yN) als: y0=h,yi+1=yi⋅gf(yi) voor i=0,1,…,N−1
Bereken tegelijkertijd de rij (d0,d1,… waarbij dk=∑i=0k−1f(yi)
Dan geldt: yi=y0⋅gf(y0)⋅gf(y1)⋅…⋅gf(yi)=h⋅gdi voor i=0,1,…,N−1
Ga door met het berekenen van nieuwe termen yi en di totdat een van de volgende twee situaties optreedt:

i) yj=xN voor bepaalde j.
Dan geldt: xN=yj⇔gb+d=h⋅gdj⇔h=gb+d−dj waaruit de gezochte n≡b+d−dj(modp) gevonden kan worden.
ii) di=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