www.wikidata.de-de.nina.az

Diskreter Logarithmus In der Gruppentheorie und Zahlentheorie ist der diskrete Logarithmus das Analogon zum gewöhnlichen

Diskreter Logarithmus

In der Gruppentheorie und Zahlentheorie ist der diskrete Logarithmus das Analogon zum gewöhnlichen Logarithmus aus der Analysis; diskret kann in diesem Zusammenhang etwa wie ganzzahlig verstanden werden. Die diskrete Exponentiation in einer zyklischen Gruppe ist die Umkehrfunktion des diskreten Logarithmus. Als Vergleich: Die natürliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des natürlichen Logarithmus.

Ein wichtiger Anwendungsfall tritt beim Rechnen modulo p auf. Der diskrete Logarithmus von zur Basis ist hier der kleinste Exponent der Gleichung bei gegebenen natürlichen Zahlen , und der Primzahl . Zum Beispiel ist beim Rechnen modulo der diskrete Logarithmus von zur Basis gleich , da ist.

Da für den diskreten Logarithmus meist nur ineffiziente (im Sinne der Komplexitätstheorie) Algorithmen bekannt sind, während sich die Umkehrfunktion, die diskrete Exponentialfunktion, leicht (im Sinne der Komplexitätstheorie) berechnen lässt, eignet sich die diskrete Exponentialfunktion als Einwegfunktion in der Kryptografie. Anwendungsbeispiele sind u. a.

Theorie Bearbeiten

Allgemeine Definition Bearbeiten

Es sei eine endliche zyklische Gruppe mit Erzeuger der Ordnung . Dann ist die diskrete Exponentiation

ein Gruppenisomorphismus. Die zugehörige Umkehrfunktion

heißt diskreter Logarithmus zur Basis .

Die bekannte Basiswechselformel bleibt gültig: Ist ein weiterer Erzeuger, dann ist

Weiterhin gilt die folgende Beziehung für den diskreten Logarithmus, die der Funktionalgleichung des Logarithmus entspricht:

Prime Restklassengruppe Bearbeiten

Von praktischem Nutzen in der Kryptografie ist der Spezialfall, wenn die zyklische Gruppe eine prime Restklassengruppe ist, insbesondere modulo Primzahlen.

Sei eine Primzahl und eine Primitivwurzel modulo , also ein Erzeuger der primen Restklassengruppe . Der diskrete Logarithmus (auch Index genannt) einer zu teilerfremden Zahl zur Basis ist definiert als die eindeutig bestimmte Zahl mit:

und wird mit bzw. bezeichnet (zur Schreibweise siehe Kongruenz (Zahlentheorie) und modulo).

Algorithmen zur Berechnung des diskreten Logarithmus Bearbeiten

Es sind bisher keine schnellen Algorithmen zur Berechnung des diskreten Logarithmus bekannt. Deren Laufzeit verhielte sich polynomial zur Länge der Eingabe. Es gibt aber Algorithmen, die die Lösung gezielter finden als bloßes Ausprobieren. Aufgrund des angesprochenen Laufzeitverhaltens und der in der Kryptografie üblichen Größenordnungen (mehrere hundert Dezimalstellen in Numerus und Basis) spielen sie praktisch aber keine Rolle. Zu den bekanntesten Algorithmen zählen:

Beispiel Bearbeiten

Als Beispiel diene die Primzahl und die zugehörige prime Restklassengruppe . Zur Primitivwurzel wird nun die Wertetabelle der diskreten Exponentiation bestimmt.

1 2 3 4 5 6 7 8 9 10
2 4 8 5 10 9 7 3 6 1

Dass es sich bei tatsächlich um eine Primitivwurzel modulo 11 handelt, ist an den paarweise verschiedenen diskreten Potenzen erkennbar. Mit anderen Worten, die gesamte prime Restklassengruppe kann mithilfe der diskreten Potenzen von erzeugt werden. Durch Vertauschen der Zeilen und Sortieren erhält man die Wertetabelle des diskreten Logarithmus.

1 2 3 4 5 6 7 8 9 10
10 1 8 2 4 9 7 3 6 5

Literatur Bearbeiten

  • Erich Härtter: Wahrscheinlichkeitsrechnung, Statistik und mathematische Grundlagen. Begriffe, Definitionen und Formeln. Verlag Vandenhoeck & Ruprecht, Göttingen 1987, ISBN 3-525-40731-9.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Gruppentheorie und Zahlentheorie ist der diskrete Logarithmus das Analogon zum gewohnlichen Logarithmus aus der Analysis diskret kann in diesem Zusammenhang etwa wie ganzzahlig verstanden werden Die diskrete Exponentiation in einer zyklischen Gruppe ist die Umkehrfunktion des diskreten Logarithmus Als Vergleich Die naturliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des naturlichen Logarithmus Ein wichtiger Anwendungsfall tritt beim Rechnen modulo p auf Der diskrete Logarithmus von m displaystyle m zur Basis a displaystyle a ist hier der kleinste Exponent x displaystyle x der Gleichung a x m mod p textstyle a x equiv m mod p bei gegebenen naturlichen Zahlen m displaystyle m a displaystyle a und der Primzahl p displaystyle p Zum Beispiel ist beim Rechnen modulo 11 textstyle 11 der diskrete Logarithmus von 5 displaystyle 5 zur Basis 2 displaystyle 2 gleich 4 textstyle 4 da 2 4 16 5 mod 11 textstyle 2 4 16 equiv 5 mod 11 ist Da fur den diskreten Logarithmus meist nur ineffiziente im Sinne der Komplexitatstheorie Algorithmen bekannt sind wahrend sich die Umkehrfunktion die diskrete Exponentialfunktion leicht im Sinne der Komplexitatstheorie berechnen lasst eignet sich die diskrete Exponentialfunktion als Einwegfunktion in der Kryptografie Anwendungsbeispiele sind u a Diffie Hellman Schlusselaustausch Elgamal Signaturverfahren Schnorr Signaturverfahren DSA Verfahren Elliptische Kurven KryptosystemInhaltsverzeichnis 1 Theorie 1 1 Allgemeine Definition 1 2 Prime Restklassengruppe 2 Algorithmen zur Berechnung des diskreten Logarithmus 3 Beispiel 4 LiteraturTheorie BearbeitenAllgemeine Definition Bearbeiten Es sei G textstyle G circ nbsp eine endliche zyklische Gruppe mit Erzeuger g textstyle g nbsp der Ordnung n textstyle n nbsp Dann ist die diskrete Exponentiation exp g Z n Z G x g x textstyle begin aligned exp g colon mathbb Z n mathbb Z amp to G x amp mapsto g x end aligned nbsp ein Gruppenisomorphismus Die zugehorige Umkehrfunktion log g G Z n Z x log g x textstyle begin aligned log g colon G amp to mathbb Z n mathbb Z x amp mapsto log g x end aligned nbsp heisst diskreter Logarithmus zur Basis g textstyle g nbsp Die bekannte Basiswechselformel bleibt gultig Ist h displaystyle h nbsp ein weiterer Erzeuger dann ist log h x log g x log h g mod n textstyle log h x log g x cdot log h g mod n nbsp Weiterhin gilt die folgende Beziehung fur den diskreten Logarithmus die der Funktionalgleichung des Logarithmus entspricht log g x log g y log g x y mod n textstyle log g x log g y log g x circ y mod n nbsp Prime Restklassengruppe Bearbeiten Von praktischem Nutzen in der Kryptografie ist der Spezialfall wenn die zyklische Gruppe eine prime Restklassengruppe ist insbesondere modulo Primzahlen Sei p textstyle p nbsp eine Primzahl und g displaystyle g nbsp eine Primitivwurzel modulo p textstyle p nbsp also ein Erzeuger der primen Restklassengruppe Z p Z textstyle mathbb Z p mathbb Z times nbsp Der diskrete Logarithmus auch Index genannt einer zu p textstyle p nbsp teilerfremden Zahl x displaystyle x nbsp zur Basis g displaystyle g nbsp ist definiert als die eindeutig bestimmte Zahl a 1 2 p 1 textstyle a in 1 2 dotsc p 1 nbsp mit g a x mod p textstyle g a equiv x mod p nbsp und wird mit a log g x textstyle a log g x nbsp bzw a ind g x textstyle a operatorname ind g x nbsp bezeichnet zur Schreibweise siehe Kongruenz Zahlentheorie und modulo Algorithmen zur Berechnung des diskreten Logarithmus BearbeitenEs sind bisher keine schnellen Algorithmen zur Berechnung des diskreten Logarithmus bekannt Deren Laufzeit verhielte sich polynomial zur Lange der Eingabe Es gibt aber Algorithmen die die Losung gezielter finden als blosses Ausprobieren Aufgrund des angesprochenen Laufzeitverhaltens und der in der Kryptografie ublichen Grossenordnungen mehrere hundert Dezimalstellen in Numerus und Basis spielen sie praktisch aber keine Rolle Zu den bekanntesten Algorithmen zahlen Babystep Giantstep Algorithmus Pohlig Hellman Algorithmus Index Calculus Algorithmus Pollard Rho Methode ZahlkorpersiebBeispiel BearbeitenAls Beispiel diene die Primzahl p 11 textstyle p 11 nbsp und die zugehorige prime Restklassengruppe G Z 11 Z 1 2 10 textstyle G mathbb Z 11 mathbb Z times 1 2 dotsc 10 nbsp Zur Primitivwurzel g 2 textstyle g 2 nbsp wird nun die Wertetabelle der diskreten Exponentiation bestimmt 2 1 2 2 mod 11 2 2 4 4 mod 11 2 3 8 8 mod 11 2 4 16 5 mod 11 2 5 32 10 mod 11 2 6 64 9 mod 11 2 7 128 7 mod 11 2 8 256 3 mod 11 2 9 512 6 mod 11 2 10 1024 1 mod 11 textstyle begin array lcrlrl 2 1 amp amp 2 amp equiv amp 2 amp mod 11 2 2 amp amp 4 amp equiv amp 4 amp mod 11 2 3 amp amp 8 amp equiv amp 8 amp mod 11 2 4 amp amp 16 amp equiv amp 5 amp mod 11 2 5 amp amp 32 amp equiv amp 10 amp mod 11 2 6 amp amp 64 amp equiv amp 9 amp mod 11 2 7 amp amp 128 amp equiv amp 7 amp mod 11 2 8 amp amp 256 amp equiv amp 3 amp mod 11 2 9 amp amp 512 amp equiv amp 6 amp mod 11 2 10 amp amp 1024 amp equiv amp 1 amp mod 11 end array nbsp a textstyle a nbsp 1 2 3 4 5 6 7 8 9 102 a mod 11 textstyle 2 a mod 11 nbsp 2 4 8 5 10 9 7 3 6 1Dass es sich bei g displaystyle g nbsp tatsachlich um eine Primitivwurzel modulo 11 handelt ist an den paarweise verschiedenen diskreten Potenzen erkennbar Mit anderen Worten die gesamte prime Restklassengruppe kann mithilfe der diskreten Potenzen von g displaystyle g nbsp erzeugt werden Durch Vertauschen der Zeilen und Sortieren erhalt man die Wertetabelle des diskreten Logarithmus x textstyle x nbsp 1 2 3 4 5 6 7 8 9 10log 2 x textstyle log 2 x nbsp 10 1 8 2 4 9 7 3 6 5Literatur BearbeitenErich Hartter Wahrscheinlichkeitsrechnung Statistik und mathematische Grundlagen Begriffe Definitionen und Formeln Verlag Vandenhoeck amp Ruprecht Gottingen 1987 ISBN 3 525 40731 9 Abgerufen von https de wikipedia org w index php title Diskreter Logarithmus amp oldid 232349642