Diskrete Logarithmen

Diskrete Logarithmen sind Lösungen von Gleichungen der Form
\(\displaystyle a^x = \underbrace{a \circ a \circ \cdots}_{x \text{-mal}} = b \)
über einer endlichen zyklischen Gruppe \(\displaystyle (G,\circ) = \langle a \rangle\). Der diskrete Logarithmus \(\displaystyle x\) von \(\displaystyle b\) zur Basis \(\displaystyle a\) ist modulo der Gruppenordnung von \(\displaystyle G\) eindeutig bestimmt und existiert - da \(\displaystyle a\) ein Erzeuger der Gruppe ist - für alle Elemente der Gruppe.
Diskrete Logarithmen sind im Sinne der Komplexitätstheorie für viele Gruppen aufwändig zu berechnen und finden Anwendung in der Kryptographie, etwa in auf elliptischen Kurven basierenden Kryptosystemen.
 
 

Beispiel

\(\displaystyle 2^x\;\mod\;11 = 5 \)
hat als Lösung den Wert 4, denn es gilt \(\displaystyle 2^{4}\) = 16, und 16 lässt den Rest 5 bei Division mit Rest durch 11. Die Lösung ist eindeutig modulo 10, also modulo der Gruppenordnung von \(\displaystyle (\mathbb Z\,/\,11 \,\mathbb Z)^\times\). Dementsprechend ist mit \(\displaystyle x\) auch \(\displaystyle x\)±10 eine Lösung der Kongruenz.

Es gibt jedoch noch einen anderen Grund für die hohe Wertschätzung der Mathematik; sie allein bietet den Naturwissenschaften ein gewisses Maß an Sicherheit, das ohne Mathematik nicht erreichbar wäre.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Logarithmus aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе