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 het discreet logaritme te vinden. De Britse wiskundige John Pollard beschreef deze methode in hetzelfde artikel als waarin hij Pollards rho-algoritme voor logaritmen beschreef.

Het discreet logaritme is gedefinieerd in een cyclische groep. Laat G een groep zijn, met orde p, en G cyclisch. Laat g \inG voortbrenger zijn van G en h\in G. Het discreet logaritme luidt nu als volgt: Bepaal de oplossing van g^n=h.

Pollards lambda-algoritme is bruikbaar om de oplossing n voor dit probleem te bepalen, als men weet dat deze waarde n in een interval {a, …b} ligt.

Door a = 0 and b = p − 1 te stellen is het is mogelijk om het Pollard lambda-algoritme voor algemene n te gebruiken, maar Pollards lambda-algoritme gaat veel sneller als {a, …b} een relatief klein interval is.

Het algoritme[bewerken]

  • We kiezen een verzameling S met gehele getallen en definiëren een functie, f(x) die de groep, G afbeeldt op deze verzameling S. (f(x) : G → S)
  • Vervolgens kiezen we een integer N en berekenen een reeks groepelementen {x_0, x_1, …,x_N} door :
x_0 = g^b
x_{i+1}= x_i\cdot  g ^{f(x_i)} voor i = 0,1,…, N-1
  • Daarna berekenen we 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 .... \cdot  g ^{f(x_{N-1})} = x_0\cdot  g ^d =  g ^b \cdot  g ^d =  g ^{b+d}
  • We berekenen nu een tweede reeks groepselementen {y_0, y_1,…y_N} door
y_0 = h
y_{i+1}= y_i\cdot  g ^{f(y_i)} voor i = 0,1,…, N-1
  • Tegelijkertijd berekenen we de rij {d_0, d_1,.....} 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 .... \cdot  g ^{f(y_{i})} = h \cdot  g ^{d_i} voor i = 0,1,…., N-1
  • We gaan door met het berekenen van nieuwe termen {y_i} en {d_i} totdat één van de volgende twee situaties optreedt:
i) y_j = x_N voor bepaalde j.
We hebben dan: x_N = y_j\Leftrightarrow
g^{b+d} = h\cdot g^{d_j} >\Leftrightarrow
h = g^{b+d-d_j} waaruit we de gezochte n ≡ b + d - d_j (mod p) kunnen berekenen.
ii) d_i > b − a + d.
Als dit gebeurt, dan 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