11^4 mod 123 effektiv berechnen

15.02.2011, 14:24

Zack

Auf diesen Beitrag antworten »

11^4 mod 123 effektiv berechnen

Meine Frage:
Hallo,
ich soll
$\begin{eqnarray*} a) 11^{4} mod 123 \end{eqnarray*}$
$\begin{eqnarray*} b) 2^{40} mod 123 \end{eqnarray*}$
$\begin{eqnarray*} c) 25^{40} mod 123 \end{eqnarray*}$
$\begin{eqnarray*} d) 50^{123} mod 123 \end{eqnarray*}$
berechnen. Bei der Aufgabe steht dabei:
"Zur Lösung von Aufgabenteil (b) kann das Ergebnis von (a) nützlich sein, für Aufgabenteil (d) die Ergebnisse von (b) und (c)"

Meine Ideen:
Meine Idee wäre Square and Multiply, aber das führt zu keinem brauchbaren schnellen Weg.
Eine andere Idee war mittels Potenz-gesetzte die erste Aufgabe um zu formen in $\begin{eqnarray*} 11^{2} \cdot 11^{2} mod 123 = 121 * 121 mod 123 \end{eqnarray*}$
Das bringt mir auch wieder nix.

Wie löse ich die Aufgabe effektiv, geht darum das ich in ner Klausur auch unter Zeitstress stehe.

15.02.2011, 15:20

kiste

Auf diesen Beitrag antworten »

Beachte 121 = - 2 (mod 123)

15.02.2011, 15:51

René Gruber

Auf diesen Beitrag antworten »

b) Beachte $\begin{eqnarray*} 123 = 3\cdot 41 \end{eqnarray*}$ , denn die Einzelberechnung $\begin{eqnarray*} 2^{40}\bmod 3 \end{eqnarray*}$ und $\begin{eqnarray*} 2^{40}\bmod 41 \end{eqnarray*}$ ist ein leichtes.

15.02.2011, 17:41

Mystic

Auf diesen Beitrag antworten »

In d) sollte die Beobachtung

$\begin{eqnarray*} 50^4 \equiv 1 \mod 123 \end{eqnarray*}$

helfen...

15.02.2011, 17:44

tmo

Auf diesen Beitrag antworten »

In c) hilft $\begin{eqnarray*} 25 = 5^2 \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(123)=80 \end{eqnarray*}$ smile

smile

Jetzt hat jeder mal was zu einer Aufgabe erwähnt Tanzen

Tanzen

15.02.2011, 17:50

Mystic

Auf diesen Beitrag antworten »

Naja, b) und c) sind wegen

$\begin{eqnarray*} \lambda(123) =kgV(3-1,41-1)=40 \end{eqnarray*}$

ohnehin keiner Erwähnung wert, aber auch d) folgt daraus (wie in der Aufgabe bereits angegeben) sehr schnell...

Anzeige

15.02.2011, 19:29

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Zur Lösung von Aufgabenteil (b) kann das Ergebnis von (a) nützlich sein

Wie ist das denn gemeint?

Ich habe mir

Zitat:

b) Beachte $\begin{eqnarray*} 123 = 3\cdot 41 \end{eqnarray*}$ , denn die Einzelberechnung $\begin{eqnarray*} 2^{40}\bmod 3 \end{eqnarray*}$ und $\begin{eqnarray*} 2^{40}\bmod 41 \end{eqnarray*}$ ist ein leichtes.

mal zu Herzen genommen und komme dann durch Klammern und ggf. durch Darstellung als "Inverse Restklasse" auf

$\begin{eqnarray*} 2^{40}\bmod 3 \equiv 1 \bmod 3 \end{eqnarray*}$ und $\begin{eqnarray*} 2^{40}\bmod 41\equiv 1 \bmod 41 \end{eqnarray*}$

Nach welcher Regel füge ich das nun wieder zusammen? Am Ende müßte man wohl erhalten:

$\begin{eqnarray*} 2^{40}\bmod 123\equiv 1 \bmod 123 \end{eqnarray*}$

Spielt da die Teilerfremdheit von 3 und 41 rein? Und dass gilt $\begin{eqnarray*} \mathbb Z_{123} \cong \mathbb Z_{3} \times \mathbb Z_{41} \end{eqnarray*}$ ?

15.02.2011, 19:45

tmo

Auf diesen Beitrag antworten »

Ja, das Entscheidende ist $\begin{eqnarray*} \mathbb Z_{123} \cong \mathbb Z_3 \times \mathbb Z_{41} \end{eqnarray*}$ , was nach dem chinesischen Restsatz gilt, da 43 und 3 teilerfremd sind.

Das bedeutet nämlich, dass das System von Kongruenzen
$\begin{eqnarray*} x \equiv 1 \pmod {41} \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 1 \pmod 3 \end{eqnarray*}$

genau eine Lösung in $\begin{eqnarray*} \{0, 1, \dotsc, 122 \} \end{eqnarray*}$ hat. Da 1 offensichtlich eine ist, ist dies auch die einzige.

Jede andere Lösung ist also kongruent zu 1 modulo 123.

Wie man bei b) die a) verwenden könnte:

Wenn man die a) gemacht hat, kommt man auf $\begin{eqnarray*} 11^4 \equiv 2^2 \pmod {123} \end{eqnarray*}$ , also ist $\begin{eqnarray*} 2^{40} \equiv 11^{80} \pmod {123} \end{eqnarray*}$ , wo dann wieder Euler-Fermat gefragt wäre.

15.02.2011, 19:55

HAL 9000

Auf diesen Beitrag antworten »

Ja, das wird's wohl sein, der Verweis auf a) sollte wohl Exponent 80 ermöglichen und damit die direkte Verwendung von Euler-Fermat.

Wie Mystic aber schon erwähnte, ist das hier gar nicht nötig, da die Argumentation auch schon mit Exponent $\begin{eqnarray*} \lambda(123) = kgV(40,2) = 40 \end{eqnarray*}$ klappt (siehe Carmichael-Funktion). Aber das ist wohl etwas weniger bekannt als Euler-Fermat. Augenzwinkern

Augenzwinkern

15.02.2011, 20:02

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Wenn man die a) gemacht hat, kommt man auf $\begin{eqnarray*} 11^4 \equiv 2^2 \pmod {123} \end{eqnarray*}$ , also ist $\begin{eqnarray*} 2^{40} \equiv 11^{80} \pmod {123} \end{eqnarray*}$ , wo dann wieder Euler-Fermat gefragt wäre.

So, also mir ist nun erst mal nicht klar, warum euch klar ist, dass das ein Fall für Euler-Fermat ist. Ups

Ups

[In meinem Algebra-Buch finde ich den gar nicht, das Zahlentheoriebuch hilft aus] Aber was sollte die Glocken klingen lassen?

Den Weg von Mystic machen wir danach. Sonst verliere ich total den Überblick.

edit:

Also wenn ich richtig rechen:

$\begin{eqnarray*} \varphi(123) = 123 \cdot (1-\frac{1}{3}) \cdot (1-\frac{1}{41}) = 80 \end{eqnarray*}$

Seht ihr das sofort (also ohne Rechnung)? Oder testet man das?

15.02.2011, 20:12

HAL 9000

Auf diesen Beitrag antworten »

Man muss sich nicht unbedingt mit Brüchen abquälen, die Rechnung

$\begin{eqnarray*} \varphi(123) = \varphi(3\cdot 41) = (3-1)\cdot (41-1) = 80 \end{eqnarray*}$

tut es ja auch. Augenzwinkern

Augenzwinkern

15.02.2011, 20:14

tigerbine

Auf diesen Beitrag antworten »

Big Laugh

Dennoch bleibt die Frage, was euch motiviert hat, den Euler-Fermat zu nehmen. Ist es die Übung, die euch deine Rechnung eh schnell im Kopf überschlagen ließ und dann: passt?

15.02.2011, 20:17

HAL 9000

Auf diesen Beitrag antworten »

Bei "großen" Exponenten wird man immer versuchen, ein Auge auf Euler-Fermat (oder eben Carmichael ... achja, das später) zu werfen - könnte ja nützlich sein. Und bei Schulbuchaufgaben ist es dann auch oft so. Big Laugh

Big Laugh

15.02.2011, 20:29

tigerbine

Auf diesen Beitrag antworten »

Also, ich versuche nun mal das was ich eben gelernt habe anzuwenden, auch wenn ihr es im Grunde schon geschrieben habt. [Das ist nun aber mehr Zahlentheorie als Algebra oder?]

Für die Carmichael-Funktion gibt es mehrere Berechnungsmöglochkeiten. Zu erst Zerlegt man die 123 in Primfaktoren. hier 123=3*41. Für Primzahlen (als Primzahlpotenz mit hoch 1) $\begin{eqnarray*} p \geq 3 \end{eqnarray*}$ ergibt sich dann $\begin{eqnarray*} \lambda(p) = p-1 \end{eqnarray*}$ . Somit folgt

$\begin{eqnarray*} \lambda(123) = \lambda(3 \cdot 41) = kgV \{ \lambda(3), \lambda(40) \} = kgV \{2,40 \} = 40 \end{eqnarray*}$

Nun ist 2 teilerfremd zu 123 und daher folgt

$\begin{eqnarray*} 2^{40} = 2^{\lambda(123)} \equiv 1 \bmod 123 \end{eqnarray*}$

15.02.2011, 20:33

HAL 9000

Auf diesen Beitrag antworten »

So ist es.

15.02.2011, 20:36

tigerbine

Auf diesen Beitrag antworten »

Tanzen

Dankeschön. Fragen zum "Rest" kommen später. Augenzwinkern

Augenzwinkern

15.02.2011, 20:45

Zack

Auf diesen Beitrag antworten »

aaah soviele Antworten,

Danke danke dank an alle Big Laugh

Big Laugh

hat mir sehr geholfen

15.02.2011, 23:45

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
In c) hilft $\begin{eqnarray*} 25 = 5^2 \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(123)=80 \end{eqnarray*}$ smile

smile

Wir nehmen also hier wieder Euler-Fermat? verwirrt

verwirrt

$\begin{eqnarray*} ggT(5,123)=1 \end{eqnarray*}$ und $\begin{eqnarray*} 25^{40}=5^{80} = 5^{\varphi(123)} \equiv 1 \bmod 123 \end{eqnarray*}$

Haben wir hier eine Zahlengröße erreicht, die z.B. matlab in die Knie zwingt? Da kommt 0 mod 123 raus. Maple liefert 1 mod 123.

Bei der d dann mit c und d

$\begin{eqnarray*} 50^{123} = 2^{123} 25^{123} = (2^{40})^3\cdot (25^{40})^3\cdot 2^3 \cdot 25^3 \equiv (8\cdot 4) \bmod 123 \end{eqnarray*}$

16.02.2011, 11:38

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Wir nehmen also hier wieder Euler-Fermat? verwirrt

verwirrt

Wie so oft in der Mathematik, sieht man die Dinge etwas klarer, wenn man einen Schritt zurücktritt und die Dinge aus einer etwas größeren Distanz betrachtet...

Es geht doch hier ganz allgemein um das Problem, in einer endliche Gruppe G (mit multiplikativer Schreibweise und Einselement e) für ein Element $\begin{eqnarray*} a \in G \end{eqnarray*}$ die Potenz $\begin{eqnarray*} a^n \end{eqnarray*}$ für ein $\begin{eqnarray*} n \in \mathbb Z \end{eqnarray*}$ möglichst effizient zu berechnen... Wie wir ja auch hier wieder gesehen haben, denkt "Otto Normalverbraucher" da zunächst einmal daran, die Beziehung

$\begin{eqnarray*} a^{|G|}=e \Rightarrow a^n = a^{n \mod |G|} \end{eqnarray*}$

zu nutzen... Fortgeschrittene werden dabei allerdings auch schon die Möglichkeit in Betracht ziehen, dass der Exponent exp(G) kleiner als |G| sein kann und falls exp(G) leicht berechenbar ist lieber

$\begin{eqnarray*} a^{exp(G)}=e \Rightarrow a^n = a^{n \mod exp(G)} \end{eqnarray*}$

verwenden... Wenn man a aber konkret kennt, sollte man sich natürlich auch damit noch nicht zufrieden geben und statt dessen mit der echten Ordnung ord(a) von a arbeiten, also

$\begin{eqnarray*} a^{ord(a)}=e \Rightarrow a^n = a^{n \mod ord(a)} \end{eqnarray*}$

benutzen... Für die Berechnung von ord(a) muss man dabei aus algorithmischer Sicht nur sukzessive "überflüssige Primfaktoren" aus exp(G) (oder |G|) entfernen... Einen Primfaktor p von k mit $\begin{eqnarray*} a^k=e \end{eqnarray*}$ nenne ich hier mal etwas salopp "überflüssig", wenn auch schon

$\begin{eqnarray*} a^{k/p}=e \end{eqnarray*}$

gilt (zu Beginn muss natürlich k:=exp(G) bzw. k:=|G| gesetzt werden)...

Konkret in unserem Beispiel $\begin{eqnarray*} G=\mathbb{Z}_{123}^{\ast} \end{eqnarray*}$ heißt dies, dass man für die mod-Reduktionen im Exponenten von vornherein nicht

$\begin{eqnarray*} |G|=\varphi(123)=(3-1)(41-1)=80 \end{eqnarray*}$

verwenden sollte, sondern

$\begin{eqnarray*} exp(G)=\lambda(123)=kgV(3-1,41-1)=40 \end{eqnarray*}$

oder (falls überhaupt notwendig, was hier in diesem Beispiel nicht zutrifft) die Ordnung ord(a)... Für a=50 sind die zugehörigen Moduln für die Reduktion des Exponenten 80, 40 bzw. 4, d.h., da ist ein Riesenunterschied...

Ich hoffe, diese Ausführungen haben etwas Klarheit in die ganze Sache hier hereingebracht... Augenzwinkern

Augenzwinkern

16.02.2011, 13:38

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Haben wir hier eine Zahlengröße erreicht, die z.B. matlab in die Knie zwingt? Da kommt 0 mod 123 raus. Maple liefert 1 mod 123.

Das wundert mich jetzt aber, selbst der Windows-Taschenrechner kriegt 5^80 mod 123 hin. Der kriegt sogar noch deutlich größere Größenordnungen hin. Der muss sich wohl im Hintergrund irgendwie merken, wie die Zahl (durch Potenzieren) enstanden ist und führt dann Square-and-Multiply aus.

@Mystic: So wie die Aufgaben gestellt waren (auch mit dem Hinweise man soll in b) die a) benutzen), würde ich davon ausgehen, dass denjenigen, die die Aufgaben lösen sollen, noch die Theorie fehlt um den Weg über den Exponenten zu gehen. Es steckt zwar nicht viel dahinter, aber es steckt was dahinter.

Und es gibt Beispiele, bei denen man sich mit dem Weg über den Exponenten gegenüber Euler-Fermat viel Arbeit spart. Die Aufgaben hier sind aber sicher kein solches Beispiel.

16.02.2011, 18:39

tigerbine

Auf diesen Beitrag antworten »

Hallo,

danke für die Ausführungen Mystic. Das was ich gemacht habe, ist nun aber nicht falsch, oder?

16.02.2011, 21:01

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
danke für die Ausführungen Mystic. Das was ich gemacht habe, ist nun aber nicht falsch, oder?

Nein, die sind natürlich in Ordnung... Freude

Freude

Sorry, wenn das zuwenig deutlich herausgekommen ist: Meine Ausführungen waren nur grundsätzlicher Natur und bringen im konkreten Fall auch kaum eine Vereinfachung...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »