Potenzen in Restklassenringen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo!
Kann mir bitte jemand nochmal kurz und ggf mit einem Rechenbeispiel erklären, wie man Potenzen in Restklassenringen berechnet? Z.B. Berechne 154^94 im [mm] \IZ_{14}
[/mm]
Also das ging mit dem Horner-schema, soviel ist klar, aber wie es dann weiterging habe ich nicht verstanden.
Danke für Hilfe im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo grave_braucht_hilfe,
> Kann mir bitte jemand nochmal kurz und ggf mit einem
> Rechenbeispiel erklären, wie man Potenzen in
> Restklassenringen berechnet? Z.B. Berechne 154^94 im
> [mm]\IZ_{14}[/mm]
154 ist in [mm]\IZ_{14}[/mm] äquivalent mit der 0.
Demzufolge [mm]154^{94}[/mm] kongruent 0 in [mm]\IZ_{14}[/mm].
Berechnung von [mm]a^{b}[/mm] in [mm]\IZ_{c}[/mm], wobei [mm]\[
ggT(a,\;c)\; = \;1[/mm]:
Stelle zunächst b als Summe von 2er-Potenzen dar.
[mm]b\; = \;\sum {\alpha _i \;2^i } [/mm]
(Binärdarstellung von b)
Berechne dann sämtliche Reste von [mm]a^{2^{i}}[/mm]:
[mm]
\begin{gathered}
a^{0} \; \equiv \;1\;\left( c \right) \hfill \\
a^{1} \; \equiv \;\beta _0 \;\left( c \right) \hfill \\
a^{2} \; \equiv \;\beta _0^2 \; \equiv \;\beta _1 \left( c \right) \hfill \\
a^{4} \; \equiv \;\beta _1^2 \; \equiv \;\beta _2 \left( c \right) \hfill \\
\end{gathered} [/mm]
für alle i, für die gilt: [mm]2^{i}\;\le\;b[/mm]
[mm]a^{b}\;\equiv\;a^{\sum {\alpha _i \;2^i }}\;\equiv\;\prod {\beta _{k} } \; \left( c \right) [/mm]
wobei die [mm]\beta_{k}[/mm] diejenigen sind, für die [mm]\alpha_{k}\;=\;1[/mm] ist.
Gruß
MathePower
|
|
|
| |
|
okay,also erstmal danke für deine hilfe! aber wirklich verstanden habe ich das leider nicht... Ich versuch's mal mit nem hoffentlich besseren Beispiel, da das erste wirklich etwas blöde gewählt war:
Berechne [mm] 19^{31} [/mm] in [mm] \IZ_{11}
[/mm]
Also der Anfang ist ja sehr leicht gemacht, keine Frage:
[19] = {..., -3, 8, 19, ...}
woraus folgt:
[mm] 19^{31} \equiv 8^{31}
[/mm]
die Binärdarstellung von 31 ist auch kein Problem:
[mm] 31_{10} [/mm] = [mm] 11111_{2}
[/mm]
Okay, soweit so gut, aber weiter komme ich nicht. Könntest du mir das bitte mal Vorrechnen? Ich verstehe auch nicht, was du mit dem Kongruenzsystem meinst.
Schonmal besten dank im Voraus, versteht sich!
Gruß Christian
|
|
|
| |
|
Hallo!
Mit MathePowers Erklärung komme ich im Moment auch nicht so ganz klar, ich weiß nicht, was er da mit [mm] \alpha_i [/mm] meint. Aber vielleicht hilft dir ja das hier.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo grave_braucht_hilfe,
> okay,also erstmal danke für deine hilfe! aber wirklich
> verstanden habe ich das leider nicht... Ich versuch's mal
> mit nem hoffentlich besseren Beispiel, da das erste
> wirklich etwas blöde gewählt war:
>
> Berechne [mm]19^{31}[/mm] in [mm]\IZ_{11}[/mm]
>
> Also der Anfang ist ja sehr leicht gemacht, keine Frage:
>
> [19] = {..., -3, 8, 19, ...}
> woraus folgt:
>
> [mm]19^{31} \equiv 8^{31}[/mm]
>
>
> die Binärdarstellung von 31 ist auch kein Problem:
> [mm]31_{10}[/mm] = [mm]11111_{2}[/mm]
Also ist:
[mm]19^{31}\;=\;19^{2^4}\; 19^{2^3}\;19^{2^2}\;19^{2^1}\;19^{2^0}[/mm]
>
> Okay, soweit so gut, aber weiter komme ich nicht. Könntest
> du mir das bitte mal Vorrechnen? Ich verstehe auch nicht,
> was du mit dem Kongruenzsystem meinst.
Das gehört zu dem Rechnen in Restklassenringen.
[mm]
\begin{gathered}
19\; \equiv \;8\;\left( {11} \right) \hfill \\
19^2 \; \equiv \;8^2 \; \equiv \;9\;\left( {11} \right) \hfill \\
19^4 \equiv \;9^2 \; \equiv 4\;\left( {11} \right) \hfill \\
19^8 \; \equiv \;4^2 \; \equiv \;5\;\left( {11} \right) \hfill \\
19^{16} \; \equiv \;5^2 \; \equiv \;3\;\left( {11} \right) \hfill \\
\end{gathered}
[/mm]
Dann kannst Du also schreiben:
[mm]
19^{31} \; \equiv \;8\; \times \;9\; \times \;4\; \times \;5\; \times 3\; \equiv \;6\; \times \;9\; \times \;3\; \equiv \;10\; \times \;3\; \equiv \;8\;\left( {11} \right)[/mm]
Gruß
MathePower
|
|
|
|
