Mathematisches Problem

[[Moepi]1]

Hallo Leute,
Heute wende ich mich mit einem etwas anderen Problem an Euch. Ich habe Probleme damit, folgende Gleichung zu beweisen:

(g^x mod p)^y mod p = (g^y mod p)^x mod p

Es sollte folgendes gelten (Vereinfacht):
p ist Primzahl, 1 < g < p, x und y = {1,2,...}


Rechnet man es für folgende Zahlen aus, so stimmt es auch:
p=7
g=2
x=1
y=2

(2^1 mod 7)^2 mod 7 = (2^2 mod 7)^1 mod 7
(2 mod 7)^2 mod 7 = (4 mod 7) mod 7
4 mod 7 = 4 mod 7
4 = 4



Multipliziert man die obige allgemeine Gleichung aus und setzt dann ein, kommt man zum selben Ergebnis:

g^xy mod p^y mod p = g^xy mod p^x mod p
2^2 mod 7^2 mod 7 = 2^2 mod 7^1 mod 7
4 mod 49 mod 7 = 4 mod 7 mod 7
4 mod 7 = 4 mod 7
4 = 4


Kann mir vielleicht jemand helfen, die obige fett/kursiv gedruckte Gleichung so umzuformen, dass man einen allgemeinen Beweis dafür hat?


PS: bei dem ganzen Scherz gehts um Diffie Hellmann.

 

[THE DEPUDEE]

Re: Methematisches Problem

1. Wer ist Diffie Hellmann ?
2. Was bedeutet "^" und "mod" ?

 

[Green Mamba]

Re: Methematisches Problem

^ ist ein Exponent, und mod ist Modulo.

 

[THE DEPUDEE]

Re: Methematisches Problem

Kenn ich nicht !
Deshalb bin ich mal lieber leise...

 

[Tomson]

Re: Methematisches Problem

^bedeutet sicherlich hoch

also x^2 = x²

was dieses mod bedeutet hab ich auch nicht gerafft

 

[[Moepi]1]

Re: Methematisches Problem

^ ist ein Exponent, und mod ist Modulo.

GreenMamba hat schon recht. Zur Lösung des Problems hab ich das mal vorausgesetzt. Und Diffie und Hellmann waren zwei Mathematiker, die ein Verfahren entwickelt haben, über welches sich aus einer Primzahl p und einem Generator g sowie zwei zufällig gewählten und geheimen natürlich Zahlen zweier Hosts ein gemeinsamer Schlüssel errechnen lässt, ohne diesen Schlüssel selbst oder Informationen, aus denen sich der Schlüssel errechnen lässt, übertragen zu müssen.

Falls es jemand von Euch schafft, hat er DH76 geknackt und wird berühmt . Aber das will ich ja garnicht, Ich will nur diese Drecksgleichung in ihrer allgemeinen Form verstehen.

 

[Loopo]

Re: Methematisches Problem

Das Knacken an sich ist ja nicht das Problem, sondern die Zeit, die man dafür aufwenden müsste!

 

[LeChris]

Re: Methematisches Problem

a mod b liefert den Rest der Ganzzahldivision a div b.

Bsp: 5 div 3 ist 1 Rest 2, denn 3*1+2=5, >>ergo 5 mod 3 = 2

Damit die Gleichung stimmt, müßte auf jeden Fall (g^x mod p)^y - (g^y mod p)^x = Z*p sein, wobei Z eine ganze Zahl ist . Vielleicht läßt sich das ja leichter beweisen...

 

[[Moepi]1]

Re: Methematisches Problem

Damit die Gleichung stimmt, müßte auf jeden Fall (g^x mod p)^y - (g^y mod p)^x = Z*p sein, wobei Z eine ganze Zahl ist . Vielleicht läßt sich das ja leichter beweisen...

Das hat mich auf ne andere Idee gebracht. Aber bitte nicht lachen, wenn das jetzt ein risen Griff ins Klo wird - ich bin mathematisch nicht so begabt. Ich weiß leider nicht so genau, was man mit ner Modulodivision alles anstellen darf und was nicht...

Ich habe am Anfang gesagt:

g^xy mod p^y mod p = g^xy mod p^x mod p


Was wäre, wenn wir folgendes sagen:
(g^xy mod p^y mod p) / (g^xy mod p^x mod p) = 1

Dann können wir doch g^xy und ein "mod p" kürzen, daraus ergibt sich:

(1 mod p^y) / (1 mod p^x) = 1

Und wenn mich nicht alles täuscht, gilt für Modulodivisionen: 1 mod x = 1, wobei x > 1 sein muss.

Wenn wir das einsetzen, ergibt sich 1 = 1 - quod erat demonstrandum


Falls ich Mist gebaut habe, sagt es mir bitte nicht, ich fühl mich grad so schlau

 

[LeChris]

Re: Methematisches Problem

Formuliere ich es mal mit einem Beispiel:

(5 mod 3)² = 4 | 25 mod 9 = 7

Was lernen wir? Der mod-Operator ist kein Multiplikator...

---

Vielleicht hilft ja der kleine fermatsche Satz: z^p mod p = z, sofern z (mal wieder ) eine ganze Zahl ist - was hier aber wohl der Fall sein sollte. Du müßtest die Operanden vor "mod p" nur mit p/p potenzieren...viel Spaß beim Weiterrechnen ...

EDIT, Denkerror: das würde wohl nur gehen, wenn die Potenz 1/p dann wieder ganzzahlig wäre......das wird wohl seltener der Fall sein...nächste Idee, irgendwer?

Referenzen (jaja, so schlau bin ich nun nicht ):
> http://de.wikipedia.org/wiki/Mod_(Mathematik) (die klauen sogar mein 5 mod 3 =2 Beispiel!)
> http://de.wikipedia.org/wiki/Kleiner_Fermatscher_Satz

 

[[Moepi]1]

Re: Methematisches Problem

Verdammt, es wäre so schön aufgegangen...