Folgerung eines Beweises < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:45 Di 14.06.2011 | | Autor: | Hanz |
Hi,
ich habe mir diesen Beweis angeschaut (Seite 6, Satz 6.5.2)
http://parsys.informatik.uni-oldenburg.de/~best/kryptographie/kry-skript-kap6b.pdf
Mir sind hier zwei Kleinigkeiten nicht ganz klar und zwar steht da im Beweis in der ersten Zeile ja: [mm] (g^{-x} [/mm] * [mm] a)^{n_p} [/mm] = [mm] g_p^{-x(p)} [/mm] * [mm] a_p [/mm] = 1
Hier verstehe ich alle Umformungen bis aus: warum darf ich von x auf x(p) schließen? Wegen der Kongruenzen, welche im Satz angegeben ist?
Und der zweite Punkt ist ganz am Ende. Man folgert ja, dass die Ordnung dieses Elements 1 ist. Dann steht da zum Schluss "Also gilt [mm] g^x [/mm] = a. Warum kann ich das anhand der Ordnung 1 folgern?
Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:58 Mi 15.06.2011 | | Autor: | felixf |
Moin!
> ich habe mir diesen Beweis angeschaut (Seite 6, Satz
> 6.5.2)
>
> http://parsys.informatik.uni-oldenburg.de/~best/kryptographie/kry-skript-kap6b.pdf
Lange nicht mehr gesehen. :)
> Mir sind hier zwei Kleinigkeiten nicht ganz klar und zwar
> steht da im Beweis in der ersten Zeile ja: [mm](g^{-x}[/mm] *
> [mm]a)^{n_p}[/mm] = [mm]g_p^{-x(p)}[/mm] * [mm]a_p[/mm] = 1
Es ist ja [mm] $(g^{-x} \cdot a)^{n_p} [/mm] = [mm] g_p^{-x} \cdot a_p$.
[/mm]
> Hier verstehe ich alle Umformungen bis aus: warum darf ich
> von x auf x(p) schließen? Wegen der Kongruenzen, welche im
> Satz angegeben ist?
Nun, es gilt doch $x [mm] \equiv [/mm] x(p) [mm] \pmod{p}$ [/mm] nach Voraussetzung. Und da [mm] $g_p$ [/mm] die Ordnung $p$ hat, ist somit [mm] $g_p^x [/mm] = [mm] g_p^{x(p)}$.
[/mm]
> Und der zweite Punkt ist ganz am Ende. Man folgert ja, dass
> die Ordnung dieses Elements 1 ist. Dann steht da zum
> Schluss "Also gilt [mm]g^x[/mm] = a. Warum kann ich das anhand der
> Ordnung 1 folgern?
In einer Gruppe gibt es genau ein Element der Ordnung 1: naemlich das neutrale Element.
Da [mm] $g^{-x} \cdot [/mm] a$ nun Ordnung 1 hat, muss [mm] $g^{-x} \cdot [/mm] a = 1$ sein. Wenn man das umformt kommt man auf [mm] $g^x [/mm] = a$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:02 Do 16.06.2011 | | Autor: | Hanz |
Achso, ja jetzt ist es mir klar. Danke!!!!
Mir ist grad eine Sache doch noch nicht ganz 100% klar und zwar:
Warum ist der ggT der einzelnen [mm] n_p [/mm] zwangsläufig gleich 1?
Liegt es daran, dass n durch die einzelnen (eigenen enthaltenen) Primzahlpotenzen geteilt wird und die entstehenden [mm] n_p [/mm] dann immer 1 als ggT haben?
Gibt es dazu irgendeinen Satz den man kennen muss?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:15 Do 16.06.2011 | | Autor: | Hanz |
Ich glaube es ist mir grad klar geworden: Der ggT zweier oder mehr Zahlen ist doch nichts anderes als gemeinsame Primzahlen, welche alle Zahlen enthalten. Bei diesen [mm] n_p [/mm] gibt es natürlich keine enzige, welche alle gemeinsam haben, weil ja gerade immer durch eine von diesen Primzahl(potenzen) geteilt wird. Also muss der ggT ja 1 sein.
|
|
|
|
![[]](/images/popup.gif){kind=small}
hier
