Discreet logaritme

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Discrete Logaritme Probleem)
Ga naar: navigatie, zoeken

Het discreet logaritme is gedefinieerd in elke cyclische groep.

Uitleg[bewerken]

Laat G een cyclische groep zijn. Laat g \in G voortbrenger zijn van G en h \in G.

Het discreet logaritme luidt nu als volgt: g^n = h, bepaal n.

Ook als de orde van G oneindig groot is worden alle elementen van G voortgebracht als machten van de voortbrenger g.
Denk bijvoorbeeld aan de verzameling \mathbb{Z}.
Het getal 1 brengt met de operatie optellen de hele groep voort.

In de praktijk wordt bij het discreet logaritme gebruikgemaakt van eindige cyclische groepen. Met het kiezen van een priemgetal voor de orde van de groep is het discreet logaritme vanwege het Pohlig-Hellman-algoritme moeilijker op te lossen.

Voorbeeld[bewerken]

G = \mathbb{F}_7^*
g = 5 is een mogelijke voortbrenger van \mathbb{F}_7^*, dus alle elementen zijn te schrijven als 5^{i}, i \in \mathbb{N}
|\mathbb{F}_7^*| = 6, de orde is dus geen priemgetal.

\begin{matrix}
5^1&=&5&&&\equiv&5&\bmod 7\\
5^2&=&25&=&3\cdot7 + 4&\equiv&4&\bmod 7\\
5^3&=&125&=&17\cdot7 + 6&\equiv&6&\bmod 7\\
5^4&=&625&=&89\cdot7 + 2&\equiv&2&\bmod 7\\
5^5&=&3125&=&446\cdot7 + 3&\equiv&3&\bmod 7\\
5^6&=&15625&=&2232\cdot7 + 1&\equiv&1&\bmod 7
\end{matrix}
5^{p-1}\equiv 1 ( mod 7).

De orde van \mathbb{F}_7^* is (p - 1)

Voor g = 5 en h = 4 geldt voor n dus n = ^5\log 4 (\bmod 7).

Zoek naar een getal dat tegelijk te schrijven is als k \cdot 7 + 4 (k \in \mathbb{N}) en als macht van 5.
Omdat p klein gekozen is, is het probleem hier gemakkelijk op te lossen. n = 2 voldoet.

Bij de keuze van een groter getal voor h zijn er verschillende mogelijkheden om de waarde van n te vinden, onder meer door gebruik te maken van de rekenregels voor logaritmen.

Voor g = 5 en h = 1953125 geldt n = ^5log(1953125) ( mod 7)

  • Omdat 1953125 = 279017\cdot 7 + 6 en dus 1953125 \equiv 6 ( mod 7), geldt n = ^5log6 ( mod 7). n = 3 voldoet.
  • Omdat 1953125 = 625 \cdot 3125 geldt n = ^5log(625 \cdot 3125 ) ( mod 7) \equiv ^5log(2 \cdot 3) ( mod 7) = ^5log6 ( mod 7) = zie bovenstaand tabelletje = 3
  • Ook geldt: n = ^5log(625 \cdot 3125 ) ( mod 7) = ^5log(5^4 \cdot 5^5) ( mod 7) = ^5log5^4( mod 7) + ^5log5^5( mod 7)= 4 + 5 = 9 \equiv 3

Het Diffie-Hellman-protocol en het Elgamal-encryptiesysteem maken gebruik van producten van machten, waarbij de afzonderlijke exponenten als geheime code verborgen kunnen blijven.

Bij keuze van een grote orde van de groep kan het probleem moeilijk opgelost worden door het maken van tabellen omdat er daarvoor veel te veel mogelijkheden zijn. De onderstaande methoden bieden mogelijkheden, te gebruiken in bijvoorbeeld \mathbb{Z}_p^*, \mathbb{F}_q^* en \mathbb{F}_{2^m}^*

Zie ook[bewerken]

Referenties[bewerken]