Pollards lambda-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

Referenties[bewerken]

  • 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