Frage von gerdax86, 120

Diskreter Logarithmus?

x = y^z mod n

x=8

y=72

n=11

8 = 72^z mod 11

Gesucht wird z, wie stelle ich das ganze um? Vielen, vielen Dank !!!!!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von ProfFrink, 26

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.

Kommentar von Schachpapa ,

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.

Kommentar von ProfFrink ,

Square-and-Multiply ist ja wirklich genial. Bin begeistert. Habe es sofort an den anderen Beispielen ausprobiert. Hat auf Anhieb hingehauen. Dann habe ich mir das nochmal genau angesehen, um es auch in der Tiefe zu begreifen. Es basiert letztlich auch auf bem binomischen Ausmultiplizieren, wobei man ja die Vielfachen von 11 "unter den Tisch fallen lassen kann". Wirklich toll, was man hier alles lernen kann.

Leider gehen solche Fähigkeiten und Kenntnisse bei der heute zur Verfügung stehen Rechenpower oft verloren. Alle noch so tollen Überlegungen zur Recheneffizienz stehen immer in Konkurrenz zur billig verfügbaren Muskelkraft unserer heutigen Rechner. Es ist schon etwas dran an der Behauptung, dass Computer dumm machen.

Antwort
von Rowal, 54

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.


Kommentar von gerdax86 ,

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

Kommentar von Rowal ,

Es ist 72=66+6. 66 ist durch 11 teilbar.

(66+6)^z wird nach dem Binomialsatz aus multipliziert und alle Glieder außer 6^z sind durch 66 also auch durch 11 teilbar und damit lässt (66+6)^z bei Division durch 11 denselben Rest wie 6^z. 

Kommentar von ProfFrink ,

Cool, hier kann man ja echt was lernen!

Antwort
von ProfFrink, 70

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
von Schachpapa, 22

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
von ProfFrink, 37

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

Kommentar von gerdax86 ,

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

Expertenantwort
von Ellejolka, Community-Experte für Mathe & Mathematik, 35
Kommentar von Ellejolka ,

nee, link geht nicht.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten