Diskrete Logarithmen

Diskrete Logarithmen sind Lösungen von Gleichungen der Form
ax=a∘a∘⋯⎵x-mal=b a^x = \underbrace{a \circ a \circ \cdots}_{x \text{-mal}} = b
über einer endlichen zyklischen Gruppe (G,∘)=⟨a⟩(G,\circ) = \langle a \rangle. Der diskrete Logarithmus xx von bb zur Basis aa ist modulo der Gruppenordnung von GG eindeutig bestimmt und existiert - da aa 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

2x  mod    11=5 2^x\;\mod\;11 = 5
hat als Lösung den Wert 4, denn es gilt 242^{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 (Z / 11 Z)×(\mathbb Z\,/\,11 \,\mathbb Z)^\times. Dementsprechend ist mit xx auch xx±10 eine Lösung der Kongruenz.

Die Logik ist die Hygiene, deren sich der Mathematiker bedient, um seine Gedanken gesund und kräftig zu erhalten.

Hermann Weyl

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е
Datenschutzerklärung

 

Elementarmathematik