Kommutativgesetz, MODULO < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Es seien x, n1 und n2 positive ganze Zahlen. Beweisen oder widerlegen Sie folgende allgemeine Aussage: (xMODn1)MODn2=(xMODn2)MODn1. |
Hallo,
Mein Lösungsansatz war, das ganze mit einem Beweis für das Kommutativgesetz zu zeigen. Leider habe ich keine Ahnung, wie das mit dem Modulo funktioniert?
Beim stupiden Ausprobieren mit eingesetzten Zahlen konnte ich schon zeigen, dass das Ergebnis auf beiden Seiten gleich ist. Aber das ist ja noch nicht wirklich ein Beweis, oder?
Hier mal ein Beispiel:
n=p*q (p und q sind Primzahlen, wie im RSA-Verfahren verlangt)
n1=11*13=143
n2=17*19=323
x=200
(200 MOD 143)MOD 323=(200 MOD 323)MOD 143
(200 MOD 143)MOD 323=57
(200 MOD 323)MOD 143=57
57=57
Aussage ist wahr.
Kann mir bitte jemand helfen, dass als allgemeinen Beweis zu formulieren?
Vielen Dank für Eure Hilfe,
Guini
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") ,
> Beim stupiden Ausprobieren mit eingesetzten Zahlen konnte ich schon zeigen, dass das Ergebnis auf beiden Seiten gleich ist. Aber das ist ja noch nicht wirklich ein Beweis, oder?
Stupide würde aber auch heißen, dass du etliche Fälle durchprobierst. Du präsentierst hier aber einen denkbar schlechten:
n2 ist hier größer als x und als n1. Das bedeutet, eine Modulo-Division verhält sich völlig neutral, egal, ob man sie zuerst oder zuletzt durchführt.
Du musst nichts beweisen, wenn du mal x=29, n1=3, n2=7 ausprobierst.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:23 Fr 16.11.2007 | | Autor: | Guiniviere |
Hallo,
vielen lieben Dank für Deine schnelle Antwort.
Durch Deine Antwort ist mir aufgefallen, dass ich mich zu sehr an das RSA geklammert habe. Da wird n ja durch p*q berechnet, wobei p und q Primzahlen sind.
In der Aufgabenstellung wird aber nur gesagt "positive, ganze Zahlen". Damit kann man ja wirklich jede x-beliebige Zahl einsetzen und kommt somit schnell daruaf, dass es nicht immer erfüllt ist.
Viele Grüße
Guini
|
|
|
|
