Pohlig-Hellman-algoritme

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 ${\displaystyle \mathbb {F} _{q}^{*}}$ van een eindig lichaam ${\displaystyle \mathbb {F} _{q}}$. Als ${\displaystyle q-1}$ het product is van kleine priemfactoren, noemt men het getal ${\displaystyle q-1}$ 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

De werking van het algoritme wordt verklaard voor de multiplicatieve groep ${\displaystyle G=\mathbb {F} _{q}^{*}}$ van het eindige lichaam ${\displaystyle \mathbb {F} _{q}}$ met als orde ${\displaystyle q}$, een priemgetal. De orde van ${\displaystyle G}$ is dan ${\displaystyle q-1}$. Zij nu ${\displaystyle g}$ een voortbrenger van ${\displaystyle G}$, dan wordt het positieve gehele getal ${\displaystyle n<q}$ gezocht, zodanig dat ${\displaystyle g^{n}=h\!\!\!\!{\pmod {q}}}$.

Het algoritme bepaalt voor elke priemfactor ${\displaystyle p_{j}}$ in de ontbinding:

${\displaystyle q-1={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\ldots {p_{i}}^{e_{i}}}$

voor ${\displaystyle n}$ een congruentievergelijking ${\displaystyle {\bmod {p}}_{j}^{e_{j}}}$. Omdat de ${\displaystyle p_{j}}$ onderling priem zijn, is er volgens de Chinese reststelling een gemeenschappelijke oplossing ${\displaystyle n}$ voor deze vergelijkingen.

Deelalgoritme

Het algoritme kan gedeeltelijk gereduceerd worden tot een algoritme dat voor de priemfactor ${\displaystyle p=p_{j}}$ een congruentievergelijking voor ${\displaystyle n}$ vindt. Daartoe schrijft men, met ${\displaystyle m=e_{j}}$:

${\displaystyle n=n_{0}+pn_{1}+\ldots +p^{m-1}n_{m-1}\!\!\!\!{\pmod {p^{m}}}}$

en bepaalt in vergelijkbare stappen successievelijk de getallen ${\displaystyle n_{j}}$ .

Vooraf worden voor ${\displaystyle j=0,1,\ldots ,p-1}$ de ${\displaystyle p}$-de-machtswortels

${\displaystyle r_{p,j}=g^{\frac {j(q-1)}{p}}}$

berekend, waaruit later teruggezocht kan worden welke ${\displaystyle j}$ bij een bepaalde waarde van deze wortels hoort. Ook wordt om ${\displaystyle n_{0}}$ te vinden ${\displaystyle h^{\frac {q-1}{p}}}$ berekend.

Volgens de kleine stelling van Fermat geldt ${\displaystyle a^{q-1}\!\!\!\!{\pmod {q}}=1}$, dus, omdat ${\displaystyle g^{n}=h\!\!\!\!{\pmod {q}}}$, volgt

${\displaystyle h^{\frac {q-1}{p}}=\left(g^{n}\right)^{\frac {q-1}{p}}=g^{\frac {n(q-1)}{p}}=g^{\frac {n_{0}(q-1)}{p}}g^{(n_{1}+n_{2}p+\ldots +n_{m-1}p^{m-2})(q-1)}=g^{\frac {n_{0}(q-1)}{p}}=r_{p,n_{0}}\!\!\!\!{\pmod {q}}}$.

Vergelijk nu ${\displaystyle h^{\frac {q-1}{p}}}$ met de berekende wortels in de lijst ${\displaystyle \{r_{p,j}\}}$ en stel ${\displaystyle n_{0}=j}$ als ${\displaystyle h^{\frac {q-1}{p}}=r_{p,j}}$.

Na ${\displaystyle n_{0}}$ moeten ${\displaystyle n_{1},n_{2},\ldots }$ gevonden worden. Om ${\displaystyle n_{1}}$ te vinden, wordt ${\displaystyle h_{1}={\frac {h}{g^{n_{0}}}}}$ gesteld.

Voor de discrete logaritme ${\displaystyle n=\log _{g}(h)}$ volgt dan

${\displaystyle n=\log _{g}(h_{1}g^{n_{0}})=\log _{g}(h_{1})+\log _{g}(g^{n_{0}})=\log _{g}(h_{1})+n_{0}.}$

Dus er ontstaat een analoog probleem

${\displaystyle h_{1}=g^{n-n_{0}}}$

en er moet gelden

${\displaystyle {h_{1}}^{\frac {q-1}{p^{2}}}=g^{\frac {(n-n_{0})(q-1)}{p^{2}}}=g^{\frac {(pn_{1}+p^{2}n_{2}+\ldots +p^{m-1}n_{m-1})(q-1)}{p^{2}}}=g^{\frac {(n_{1}+pn_{2}+\ldots +p^{m-2}n_{m-1})(q-1)}{p}}=g^{\frac {n_{1}(q-1)}{p}}=r_{p,n_{1}}.}$

Vergelijk nu ${\displaystyle {h_{1}}^{\frac {q-1}{p^{2}}}}$ met de lijst ${\displaystyle \{r_{p,j}\}}$ en stel ${\displaystyle n_{1}=j}$ als ${\displaystyle {h_{1}}^{\frac {q-1}{p^{2}}}=r_{p,j}.}$

Op deze manier worden alle ${\displaystyle n_{k}}$ gevonden voor ${\displaystyle k=1,2,\ldots ,m-1.}$ Om ${\displaystyle n_{k}}$ te vinden, stelt men

${\displaystyle h_{k}={\frac {h}{g^{n_{0}+pn_{1}+\ldots +p^{k-1}n_{k-1}}}}}$.

De discrete logaritme ${\displaystyle n=\log _{g}(h)}$ wordt dan

${\displaystyle n\equiv n_{0}+pn_{1}+\ldots +p^{k-1}n_{k-1}\!\!\!\!{\pmod {p^{i}}}}$.

Hieruit volgt

${\displaystyle h_{k}=g^{n-n_{0}-n_{1}-\ldots -p^{k-1}n_{k-1}}}$

en dus

${\displaystyle {h_{k}}^{\frac {q-1}{p^{k}}}=1}$

en ${\displaystyle {h_{k}}^{\frac {q-1}{p^{k+1}}}=r_{p,n_{k}}}$.

Vergelijk vervolgens ${\displaystyle {h_{k}}^{\frac {q-1}{p^{k+1}}}}$ met de lijst ${\displaystyle \{r_{p,j}\}}$ en stel ${\displaystyle n_{k}=j}$ als ${\displaystyle {h_{k}}^{\frac {q-1}{p^{k+1}}}=r_{p,j}}$.

Zo is voor elk van de ${\displaystyle p=p_{j}}$ een congruentievergelijking voor ${\displaystyle n}$ gevonden:

${\displaystyle n\equiv n_{0}+pn_{1}+\ldots +p^{i-1}n_{i-1}\!\!\!\!{\pmod {p^{i}}}}$.

Aangezien de ${\displaystyle p_{j}}$ onderling priem zijn, hebben deze vergelijkingen volgens de Chinese reststelling een eenduidige oplossing.

Voorbeelden

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

Gevraagd ${\displaystyle n}$ te berekenen waarvoor ${\displaystyle 2^{n}\equiv 28{\pmod {37}}}$. Hier is ${\displaystyle q=37}$ en de ontbinding van ${\displaystyle q-1}$ is ${\displaystyle q-1=36=2^{2}\times 3^{2}}$, een ontbinding met kleine priemfactoren 2 en 3. Vanwege de exponenten die bij de priemfactoren staan (beide 2), worden voor zowel ${\displaystyle p=2}$ als ${\displaystyle p=3}$ naar congruenties ${\displaystyle n=n_{0}+pn_{1}}$ gezocht.

Voor de beide priemdelers zijn de lijsten ${\displaystyle \{r_{2,j}\}=\{1,36\}}$ en ${\displaystyle \{r_{3,j}\}=\{1,26,10\}}$, want ${\displaystyle 2^{0}\!\!\!\!{\pmod {37}}=1,\ \ 2^{18}\!\!\!\!{\pmod {37}}=36}$, etc.

Stel ${\displaystyle h=2^{n}=28\!\!\!\!{\pmod {37}}}$ en bereken ${\displaystyle {28}^{36/2}=1\!\!\!\!{\pmod {37}}}$

Dan geldt ${\displaystyle 1=h^{18}={2^{n}}^{36/2}=2^{18n}=2^{18n_{0}}=r_{2,n_{0}}}$. Hieruit volgt ${\displaystyle n_{0}=0}$.

Bereken nu ${\displaystyle h_{1}=28/2^{0}=28}$ en daarmee ${\displaystyle {28}^{36/2^{2}}=-1\!\!\!\!{\pmod {37}}=r_{2,n_{1}}}$. Hieruit volgt ${\displaystyle n_{1}=1}$. Voor ${\displaystyle p=2}$ wordt de congruentie dus ${\displaystyle n=0+2\times 1=2\!\!\!\!{\pmod {4}}}$.

Voor ${\displaystyle p=3}$ berekent men ${\displaystyle {28}^{36/3}=26{\pmod {37}}=r_{3,n_{0}}}$. Hieruit volgt ${\displaystyle n_{0}=1}$.

Bereken nu ${\displaystyle h_{1}=28/2^{1}=14}$ en daarmee ${\displaystyle {14}^{36/3^{2}}=10{\pmod {37}}=r_{3,n_{1}}}$. Hieruit volgt ${\displaystyle n_{1}=2}$. Voor ${\displaystyle p=3}$ wordt de congruentie dus ${\displaystyle n=1+3\times 2=7{\pmod {9}}}$. Het stelsel congruentievergelijking dat opgelost kan worden met de Chinese reststelling, is dus

${\displaystyle n\equiv 2{\pmod {4}}}$

${\displaystyle n\equiv 7{\pmod {9}}}$

en heeft als unieke oplossing ${\displaystyle n=34}$.

Voorbeeld 2

Gevraagd ${\displaystyle n}$ te berekenen waarvoor ${\displaystyle 6^{n}=7531\!\!\!\!{\pmod {8101}}}$. De ontbinding van ${\displaystyle q-1}$ is ${\displaystyle 8101-1=8100=2^{2}\times 3^{4}\times 5^{2}}$ en er zijn weer alleen kleine priemfactoren.

${\displaystyle \{r_{2,j}\}=\{1,-1\};\{r_{3,j}\}=\{1,5883,2217\},\{r_{5,j}\}=\{1,3547,356,7077,5221\}}$.

Voor ${\displaystyle p=2}$:

${\displaystyle 7531^{8100/2}=-1{\pmod {8101}}=r_{2,1}}$ dus ${\displaystyle n_{0}=1}$.

${\displaystyle h_{1}=7531/6=8006{\pmod {8101}}}$

en

${\displaystyle 8006^{8100/2^{2}}=1{\pmod {8101}}=r_{2,0}}$ dus ${\displaystyle n_{1}=0}$

Voor ${\displaystyle p=3}$ geldt een exponent 4, wat betekent dat de congruentievergelijking die we zoeken van de vorm

${\displaystyle n=n_{0}+3n_{1}+3^{2}n_{2}+3^{3}n_{3}{\pmod {3^{4}}}}$

is. Gezocht worden dus ${\displaystyle n_{0},n_{1},n_{2},n_{3}}$. De lijst met vergelijkingswaarden is ${\displaystyle \{r_{3,j}\}=\{1,5883,2217\}}$.

${\displaystyle 7531^{8100/3}=2217{\pmod {8101}}=r_{3,2}}$ dus ${\displaystyle n_{0}=2}$.

${\displaystyle h_{1}=7531/6^{2}=6735{\pmod {8101}}}$

en vervolgens

${\displaystyle 6735^{8100/3^{2}}=1{\pmod {8101}}=r_{3,0}}$ dus ${\displaystyle n_{1}=0}$.

${\displaystyle 6735^{8100/3^{3}}=2217{\pmod {8101}}=r_{3,2}}$ dus ${\displaystyle n_{2}=2}$.

${\displaystyle 6735/6^{18}=6992{\pmod {8101}}}$

en

${\displaystyle 6992^{8100/3^{4}}=5883{\pmod {8101}}=r_{3,1}}$ dus ${\displaystyle n_{3}=1}$.

De congruentievergelijking is dan

${\displaystyle n\equiv 2+0\times 3+2\times 3^{2}+1\times 3^{3}=47{\pmod {81}}}$.

Opgemerkt zij nog dat na de berekening van ${\displaystyle n_{2}}$ we een aanpassing moeten maken. In de theorie staat dat ${\displaystyle h_{i}}$ gevonden kan worden door h te delen door ${\displaystyle g^{n_{0}+pn_{1}+p^{2}n_{2}+...+p^{i-1}n_{i-1}}}$. We hadden dus om 6992 (mod 8101) te vinden ook de deling ${\displaystyle {\frac {7531}{6^{20}}}}$ kunnen doen. Hier hebben we dat niet gedaan, maar na elke stap het grondtal waarmee we rekenen omgebouwd, op het moment dat de gevonden n_i 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 ${\displaystyle p=5\quad n_{0}}$ en ${\displaystyle n_{1}}$ berekend worden.

${\displaystyle {7531}^{8100/5}=5221{\pmod {8101}}=r_{5,4}}$, dus ${\displaystyle n_{0}=4}$.

${\displaystyle h_{1}=7531/6^{4}=7613{\pmod {8101}}}$, dus ${\displaystyle n_{1}=2}$.

De derde congruentievergelijking is hiermee gevonden en het stelsel wordt dan

${\displaystyle n\equiv 1{\pmod {4}}}$

${\displaystyle n\equiv 47{\pmod {81}}}$

${\displaystyle n\equiv 14{\pmod {25}}}$

De unieke oplossing van dit stelsel is :${\displaystyle n=6689}$.

Voorbeeld 3

Gevraagd ${\displaystyle n}$ te berekenen waarvoor ${\displaystyle 71^{n}=210\!\!\!\!{\pmod {251}}}$. De ontbinding van ${\displaystyle q-1}$ is ${\displaystyle 251-1=250=2\times 5^{3}}$ en er zijn weer alleen kleine priemfactoren.

${\displaystyle \{r_{2,j}\}=\{1,-1\};\{r_{5,j}\}=\{1,20,149,19,113\}}$.

Voor ${\displaystyle p=2}$:

${\displaystyle 210^{250/2}\equiv 250\equiv -1{\pmod {251}}=r_{2,1}}$ dus ${\displaystyle n_{0}=1}$.

Voor ${\displaystyle p=5}$ geldt een exponent 3, wat betekent dat de congruentievergelijking die we zoeken van de vorm

${\displaystyle n=n_{0}+5n_{1}+25n_{2}}$

is. Gezocht worden dus ${\displaystyle n_{0},n_{1},n_{2}}$.

${\displaystyle 210^{250/5}=149{\pmod {251}}=r_{5,2}}$ dus ${\displaystyle n_{0}=2}$.

${\displaystyle h_{1}=210/{{71}^{2}}=10{\pmod {251}}}$

en vervolgens

${\displaystyle 10^{250/5^{2}}=113{\pmod {251}}=r_{5,4}}$ dus ${\displaystyle n_{1}=4}$.

${\displaystyle h_{2}=10/{71}^{20}=231{\pmod {251}}}$

en

${\displaystyle 231^{250/125}=149{\pmod {251}}=r_{5,2}}$ dus ${\displaystyle n_{2}=2}$.

De beide congruentievergelijkingen zijn

${\displaystyle n\equiv 1{\pmod {2}}}$

${\displaystyle n\equiv 72{\pmod {125}}}$

met de unieke oplossing ${\displaystyle n=197}$.

Zie ook

• Baby-steps giant-steps algoritme
• Index calculus algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme

Referenties

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