Rechenhilfe: Kongruenzen mod n < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:37 Mo 09.07.2007 | | Autor: | xenos |
Hallo Allerseits!
Ich bekam die Aufgabe [mm] 25^{7} [/mm] mod 33 zu lösen. Dabei sollten keine Rechenhilfsmittel benutzt werden. Also machte ich mich auf die Suche nach Kongruenzen, da diese Aufgabe ansonsten von Hand nur schwer zu lösen ist.
Dabei stieß ich auf folgende Zusammenhänge:
1) a [mm] \equiv [/mm] b (mod c) [mm] \gdw [/mm] a*x [mm] \equiv [/mm] b*x (mod c)
2) [mm] a^{b} \equiv a^{\bruch{1}{n}*n*b} [/mm] (mod c)
anhand der letzteren Kongruenz habe ich also das Problem auf
[mm] 5^{14} [/mm] mod 33 reduziert. Doch spätestens hier stecke ich fest.
- kennt jemand weitere hilfreiche Kongruenzen?
- sind die von mir gefundenen Kongruenzen richtig?
- Ein Kommilitone meinte, man könne zur Lösung den chinesischen Restsatz anwenden, was ich aber nicht nachvollziehen kann. Weis jemand, wie man da Licht in Dunkel bringt?
Vielen Dank im Vorraus!
Grüße Xenos
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:20 Mo 09.07.2007 | | Autor: | statler |
Hi xenos, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Ich bekam die Aufgabe [mm]25^{7}[/mm] mod 33 zu lösen. Dabei sollten
> keine Rechenhilfsmittel benutzt werden. Also machte ich
> mich auf die Suche nach Kongruenzen, da diese Aufgabe
> ansonsten von Hand nur schwer zu lösen ist.
>
> Dabei stieß ich auf folgende Zusammenhänge:
>
> 1) a [mm]\equiv[/mm] b (mod c) [mm]\gdw[/mm] a*x [mm]\equiv[/mm] b*x (mod c)
[mm] \gdw [/mm] nur, wenn (x, c) = 1
> 2) [mm]a^{b} \equiv a^{\bruch{1}{n}*n*b}[/mm] (mod c)
[mm] a^{\bruch{1}{n}} [/mm] ist nicht unbedingt definiert
> anhand der letzteren Kongruenz habe ich also das Problem
> auf
> [mm]5^{14}[/mm] mod 33 reduziert.
Das ist richtig, weil man einfach einsetzen kann, die obigen Bemerkungen braucht man dazu nicht.
> Doch spätestens hier stecke ich
> fest.
>
> - kennt jemand weitere hilfreiche Kongruenzen?
> - sind die von mir gefundenen Kongruenzen richtig?
Jetzt ist es eierleicht: [mm] 25^{7} \equiv (5^{2})^{7} \equiv (-8)^{7} \equiv ((-2)^{3})^{7} \equiv -2^{21} \equiv -(2^{5})^{4}*2 \equiv -(-1)^{4}*2 \equiv [/mm] -2 [mm] \equiv [/mm] 31
So nachvollziehbar?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:54 Mo 09.07.2007 | | Autor: | xenos |
Vielen Dank, die Lösung ist wirklich einfach (Wenn man weis, wie es geht  ) und m.E. auch richtig.
Ich habe dazu noch weitere Fragen:
- Welche Möglichkeiten habe ich, wenn mein Exponent eine Primzahl ist? (z.B. für RSA)
- Ist die unter 1) genannte Kongruenz komplett falsch, oder gilt die Beziehung lediglich in eine Richtung?
Ursprünglich hatte ich diese Kongruenz formuliert als:
a mod c = b [mm] \Rightarrow [/mm] a*2 mod c = b*2 mod c [mm] \Rightarrow [/mm] a*x mod c = b*x mod c
Und dann noch
> 1) a $ [mm] \equiv [/mm] $ b (mod c) $ [mm] \gdw [/mm] $ a*x $ [mm] \equiv [/mm] $ b*x (mod c)
$ [mm] \gdw [/mm] $ nur, wenn (x, c) = 1
Dann würde ja nicht nur Kongruenz, sondern auch Äquivalenz gelten, oder?
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:34 Mi 11.07.2007 | | Autor: | rainerS |
Hallo xenos!
> - Welche Möglichkeiten habe ich, wenn mein Exponent eine
> Primzahl ist? (z.B. für RSA)
Da gilt zum Beispiel der ![[]](/images/popup.gif) kleine Fermatsche Satz: [mm]a^p \equiv a \pmod{p}[/mm] für alle ganzen Zahlen a und Primzahlen p.
Allerdings sind bei RSA die Exponenten im Allgemeinen keine Primzahlen. Man wählt für den Exponenten e (der zum öffentlichen Schlüssel gehört) oft eine Primzahl, aber das ist nicht immer so.
> - Ist die unter 1) genannte Kongruenz komplett falsch,
> oder gilt die Beziehung lediglich in eine Richtung?
In eine Richtung: [mm] a\equiv b \pmod{m} \implies a*x \equiv b*x \pmod{m} [/mm]. Dass die Umkehrung nicht gilt, siehst du zum Beispiel am Fall [mm] x = m [/mm], denn dann gilt für beliebige a,b: [mm]a*m \equiv b*m \pmod{m} [/mm].
Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:57 Mi 11.07.2007 | | Autor: | xenos |
Ich denke, ich habe es jetzt verstanden.
Vielen Dank!
|
|
|
|
