Discrete logaritme

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

Binnen de wiskunde is de discrete logaritme het equivalent, binnen een eindige verzameling, van de gewone logaritme op de verzameling van de reële getallen. De discrete 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.

De discrete logaritme is gedefinieerd als volgt: als g^n = h, dan is n de discrete logaritme van h, met grondtal g, in formulevorm: n = \, ^g \log h.

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 de discrete logaritme gebruikgemaakt van eindige cyclische groepen. Met het kiezen van een priemgetal voor de orde van de groep is de discrete logaritme vanwege de Pohlig-Hellman-algoritme moeilijker op te lossen.

Voorbeeld[bewerken]

G = ( \{1, 2, \ldots 6\} ,* mod 7), de cyclische groep die bestaat uit de getallen \{1, 2, \ldots 6\} met als groepsbewerking de vermenigvuldiging modulo 7.

g = 5 is een mogelijke voortbrenger van G, dus alle elementen zijn te schrijven als 5^{i}, i \in \mathbb{N}

\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}

De orde van G is 6, in formulevorm: |G| = 6.

Neem nu g = 5 en h = 4; gezocht is het getal n waarvoor geldt dat n = ^5\log 4 \, \, (\bmod \, 7).

Zoek hiervoor eerst naar een getal s dat tegelijk te schrijven is als k \cdot 7 + 4 (k \in \mathbb{N}) en als macht van 5.
Er geldt dan namelijk dat s = 5^n  \equiv 4  \, \,  (\bmod \, 7).

Omdat p klein gekozen is, is het probleem hier gemakkelijk op te lossen: s = 25 voldoet, dus n = 2.

Grotere h[bewerken]

Bij de keuze van een groter getal voor h, een getal dat zich mogelijks zelfs buiten de groep G bevindt, 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 = ^5 \log(1953125) \,  \,  (\bmod \, 7)

  • Omdat  1953125 = 279017 \cdot 7 + 6 en dus  1953125 \equiv 6 \,  \, ( \bmod \, 7) geldt n = ^5 \log6 \, \, (\bmod \, 7) \, Dus n = 3, conform bovenstaand tabelletje.
  • Omdat  1953125 = 625 \cdot 3125 geldt n = ^5 \log(625 \cdot 3125 ) \, \, ( \bmod \, 7) \equiv \, ^5 \log(2 \cdot 3) \, \, ( \bmod \, 7) = \, ^5 \log6 \,  \,  ( \bmod \, 7) = 3
  • Ook geldt: n = \, ^5\log(625 \cdot 3125 ) \, \, ( \bmod \, 7) = \, ^5 \log(5^4 \cdot 5^5) \,  \,  ( \bmod \, 7) = \, ^5 \log 5^4 \, \, ( \bmod \, 7) + \, ^5\log 5^5 \,  \,  (\bmod \, 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]