Diskreter Logarithmus?

... komplette Frage anzeigen

6 Antworten

Es gibt in Wirklichkeit sogar eine ganze Lösungsfolge.

z = 7, 17, 27, 37, ...

und somit unendlich viele Lösungen. Ich habe den interessanen Ansatz von Rowal mal aufgegriffen und mit meinem geliebten Excel mal höhere Potenzen nachgerechnet. Dabei zeigt sich dass die Restwerte eine Periodizät von 10 haben. Hier die Excelausarbeitung

https://dl.dropboxusercontent.com/u/22840008/diskreter%20Logarithmus.xlsx

Hier ein Beispiel

6^57 = 226.267.027.688.376.192.080.197.927.193.400.943.822.503.936

226.267.027.688.376.192.080.197.927.193.400.943.822.503.936/11 =

20.569.729.789.852.381.098.199.811.563.036.449.438.409.448 Rest 8

Wer Lust hat kann es ja mal nachrechnen.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Schachpapa
25.03.2016, 18:56

Um große Zahlen zu vermeiden machst du dir zunutze dass

57 = 32 + 16 + 8 + 1 = (((((1*2)+1)*2+1)*2+0)*2+0)*2+1

ist und rechnest mit kleineren Zwischenergebnissen:

1 32:  1   * 6         
1 16:  6^2 * 6 mod 11 = 7
1 8:  7^2 * 6 mod 11 = 8
0 4:  8^2    mod 11 = 9
0 2:  9^2     mod 11 = 4
1 1:  4^2 * 6 mod 11 = 8

D.h. du ermittelst die Binärdarstellung des Exponenten, fängst mit 1 an, quadrierst bei jedem Schritt und wenn in der Binärdarstellung eine 1 steht, multiplizierst du zusätzlich mit der Basis. Nach jedem Zwischenschritt rechnest du mit dem Rest weiter. So hast du immer kleine Zahlen. Funktioniert immer, nennt sich binäre Exponentiation (auch Square-and-Multiply) und ist z.B. in Python eine eingebaute Funktion.

1

Für etwas größere Zahlen gibt es den sog. Baby-Step-Giant-Step Algorithmus. Der ist deutlich besser als stumpfes Ausprobieren, aber immer noch zu langsam, um richtig großen Zahlen (> 100 Stellen) beizukommen. Diskrete Logarithmen werden z.B. bei elektronischen Unterschriften (ElGamal Verfahren) verwendet.

Antwort bewerten Vielen Dank für Deine Bewertung

Ich stimme im Prinzip @ProfFrink zu. Aber man kann  die Größe der Zahlen reduzieren. Beispielsweise genügt es die Kongruenz

6^z kongruent 8 mod 11

zu lösen. Man kommt dann ebenfalls auf z=7 als einfachste Lösung, aber mit weniger großen Zahlen.


Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von gerdax86
23.03.2016, 21:41

Danke für den Ansatz, aber wo kommt die 6 her ?

0

Wer es schafft diese Gleichung nach z umzustellen, dem winkt ein hohes Preisgeld und ein Lehrstuhl in Mathematik.

Soweit ich weiss ist der diskrete Logarithmus eines der grossen ungelösten Probleme der Mathematik. Es gibt sogar Verschlüsselungsalgorithmen, die auf die Nichtauflösbarkeit dieser Gleichung aufbauen.

All diese System könnte man an dem Tag, wo Du diese Gleichung auflöst auch gleich in die Tonne treten.

Antwort bewerten Vielen Dank für Deine Bewertung

Trotzdem kann man diese Gleichung lösen. Aber nur mit roher Gewalt. Also mit Excel und der eingebauten Restfunktion. Es kommt

z = 7

heraus.

72 hoch 7 = 10.030.613.004.288

10.030.613.004288:11 = 911.873.909.480,72727272727272727272...

911.873.909.480 x 11 = 10.030.613.004.280

 10.030.613.004.288
-10.030.613.004.280
================
                                8

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von gerdax86
23.03.2016, 21:37

Genau das ist das Ding ;) Habe es auch nur so rausgefunden. Wenn die Zahlen "klein" bleiben geht das. Danke, hat mir geholfen !!!

0

Was möchtest Du wissen?