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 behoort.

Door en te stellen is het mogelijk om het Pollard lambda-algoritme voor algemene te gebruiken, maar Pollards lambda-algoritme gaat veel sneller als 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 als: en voor .
Berekenen daarna de som van alle afzonderlijke :
Er geldt nu dus:

Berekenen nu een tweede reeks groepselementen als: voor
Bereken tegelijkertijd de rij waarbij
Dan geldt: voor
Ga door met het berekenen van nieuwe termen en totdat een van de volgende twee situaties optreedt:

i) voor bepaalde .
Dan geldt: waaruit de gezochte gevonden kan worden.
ii)
Wanneer dit gebeurt, kan 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