Logarithmus

Diskrete Logarithmen

Diskrete Logarithmen sind Lösungen von Gleichungen der Form

über einer endlichen zyklischen Gruppe . Der diskrete Logarithmus x von b zur Basis a ist modulo der Gruppenordnung von G eindeutig bestimmt und existiert – da 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:

2^x bmod 11 = 5

hat als Lösung den Wert 4, denn es gilt 2⁴ = 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 . Dementsprechend ist mit x auch x±10 eine Lösung der Kongruenz.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Logarithmus aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung