Pohlig-Hellman-algoritme

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Pohlig-Hellman algoritme)
Ga naar: navigatie, zoeken

Het Pohlig-Hellman algoritme is een algoritme om de discrete logaritme zoals die is gedefinieerd in een cyclische groep, te berekenen. In het bijzonder vindt het algoritme toepassing op de multiplicatieve groep van een eindig lichaam . Als het product is van kleine priemfactoren, noemt men het getal glad en is het Polig-Hellman-algoritme een geschikte methode om deze discrete logaritme te berekenen.

Het algoritme werd ontwikkeld door Roland Silver, maar voor het eerst, onafhankelijk van Silver, gepubliceerd door Stephen Pohlig en Martin Hellman.

Het belang van deze methode is dat de hoeveelheid rekenwerk niet afhangt van de orde van de groep, maar van de grootste factor in de orde. Het nadeel is dat de orde gefactoriseerd moet worden in priemfactoren en een dergelijke factorisatie in het algemeen moeilijk vast te stellen is.

Algoritme[bewerken]

De werking van het algoritme wordt verklaard voor de multiplicatieve groep van het eindige lichaam met als orde , een priemgetal. De orde van is dan . Zij nu een voortbrenger van , dan wordt het positieve gehele getal gezocht, zodanig dat .

Het algoritme bepaalt voor elke priemfactor in de ontbinding:

voor een congruentievergelijking . Omdat de onderling priem zijn, is er volgens de Chinese reststelling een gemeenschappelijke oplossing voor deze vergelijkingen.

Deelalgoritme[bewerken]

Het algoritme kan gedeeltelijk gereduceerd worden tot een algoritme dat voor de priemfactor een congruentievergelijking voor vindt. Daartoe schrijft men, met :

en bepaalt in vergelijkbare stappen successievelijk de getallen .

Vooraf worden voor de -de-machtswortels

berekend, waaruit later teruggezocht kan worden welke bij een bepaalde waarde van deze wortels hoort. Ook wordt om te vinden berekend.

Volgens de kleine stelling van Fermat geldt , dus, omdat , volgt

.

Vergelijk nu met de berekende wortels in de lijst en stel als .

Na moeten gevonden worden. Om te vinden, wordt gesteld.

Voor de discrete logaritme volgt dan

Dus er ontstaat een analoog probleem

en er moet gelden

Vergelijk nu met de lijst en stel als

Op deze manier worden alle gevonden voor Om te vinden, stelt men

.

De discrete logaritme wordt dan

.

Hieruit volgt

en dus

en .

Vergelijk vervolgens met de lijst en stel als .

Zo is voor elk van de een congruentievergelijking voor gevonden:

.

Aangezien de onderling priem zijn, hebben deze vergelijkingen volgens de Chinese reststelling een eenduidige oplossing.

Voorbeelden[bewerken]

Hier volgen enkele voorbeelden met kleine getallen om met het algoritme een discrete logaritme te bepalen. In de praktijk rekent men uiteraard met veel grotere getallen om de aanvallen van hackers af te slaan.

Voorbeeld 1[bewerken]

Gevraagd te berekenen waarvoor . Hier is en de ontbinding van is , een ontbinding met kleine priemfactoren 2 en 3. Vanwege de exponenten die bij de priemfactoren staan (beide 2), worden voor zowel als naar congruenties gezocht.

Voor de beide priemdelers zijn de lijsten en , want , etc.

Stel en bereken

Dan geldt . Hieruit volgt .

Bereken nu en daarmee . Hieruit volgt . Voor wordt de congruentie dus .

Voor berekent men . Hieruit volgt .

Bereken nu en daarmee . Hieruit volgt . Voor wordt de congruentie dus . Het stelsel congruentievergelijking dat opgelost kan worden met de Chinese reststelling, is dus

en heeft als unieke oplossing .

Voorbeeld 2[bewerken]

Gevraagd te berekenen waarvoor . De ontbinding van is en er zijn weer alleen kleine priemfactoren.

.

Voor :

dus .

en

dus

Voor geldt een exponent 4, wat betekent dat de congruentievergelijking die we zoeken van de vorm

is. Gezocht worden dus . De lijst met vergelijkingswaarden is .

dus .

en vervolgens

dus .
dus .

en

dus .

De congruentievergelijking is dan

.

Opgemerkt zij nog dat na de berekening van we een aanpassing moeten maken. In de theorie staat dat gevonden kan worden door h te delen door . We hadden dus om 6992 (mod 8101) te vinden ook de deling kunnen doen. Hier hebben we dat niet gedaan, maar na elke stap het grondtal waarmee we rekenen omgebouwd, op het moment dat de gevonden ni een getal ongelijk 0 opleverde. Je moet dan wel rekening houden met welke i je bezig bent, om die goed te verrekenen in de exponent bij 6.

Tot slot moeten voor en berekend worden.

, dus .
, dus .

De derde congruentievergelijking is hiermee gevonden en het stelsel wordt dan

De unieke oplossing van dit stelsel is :.

Voorbeeld 3[bewerken]

Gevraagd te berekenen waarvoor . De ontbinding van is en er zijn weer alleen kleine priemfactoren.

.

Voor :

dus .

Voor geldt een exponent 3, wat betekent dat de congruentievergelijking die we zoeken van de vorm

is. Gezocht worden dus .

dus .

en vervolgens

dus .

en

dus .

De beide congruentievergelijkingen zijn

met de unieke oplossing .

Zie ook[bewerken]

Referenties[bewerken]

  1. S. Pohlig en M. Hellman "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Transactions on Information Theory 24 (1978), pp. 106-110.
  2. N. Koblitz "A Course in Number Theory and Cryptography, Graduate Texts in Mathematics 114 (1994), pp. 102-103