Berechnung hoher Zahlen mit Modulo

Neue Frage »

09.05.2009, 11:23	Rumpfi	Auf diesen Beitrag antworten »
Berechnung hoher Zahlen mit Modulo Ich muss eine Lösung zu folgender Rechnung finden: $\begin{eqnarray} x\equiv 178^{19} (2173) \end{eqnarray}$ Das ist der Vorgang, den ich schon geschafft habe: $\begin{eqnarray} x\equiv 178^{19} = ((((178^{2})^{2})^{2}178)^{2}178) mod 2173 \end{eqnarray}$ Könnt ihr mir den Rechenvorgang Schritt für Schritt zur Lösung erklären? Ich weiß, dass als ergebnis 899 rauskommt, aber den Weg dorthin weiß ich nicht. Danke im Vorraus mfg Rumpfi
09.05.2009, 11:36	AD	Auf diesen Beitrag antworten »
Ich verstehe nicht ganz: Willst du erklärt haben, wieso $\begin{eqnarray} x\equiv 178^{19} = ((((178^{2})^{2})^{2}178)^{2}178) \mod 2173 \end{eqnarray}$ gilt, oder wie man anschließend von der rechten Seite zum Wert 899 kommt?
09.05.2009, 11:43	Rumpfi	Auf diesen Beitrag antworten »
Du kannst es so betrachten. Ich will wissen, wie man den Restbetrag von 178^19 / 2173 kommt. Modulo steht doch für rest, oder?
09.05.2009, 11:50	AD	Auf diesen Beitrag antworten »
Ja. Ich schreib mal die ersten zwei relevanten Schritte auf: $\begin{eqnarray} 178^2 &=& 31684 \equiv 1262 \mod 2173\\ 178^4 &=& (178^2)^2 \equiv 1262^2 = 1592644 \equiv 2008 \mod 2173 \end{eqnarray}$
09.05.2009, 11:55	Rumpfi	Auf diesen Beitrag antworten »
Diese Methode wird mich bei der Klausur viel Zeit kosten, aber trotzdem danke.
09.05.2009, 12:15	AD	Auf diesen Beitrag antworten »
Das "trotzdem" klingt immer so: Wieso hast du nichts besseres geboten? Deswegen verzichte ich gern auf dieses "trotzdem danke".
Anzeige

09.05.2009, 12:26	Bjoern1982	Auf diesen Beitrag antworten »
@ Arthur Das denk ich mir bei solchen Formulierungen auch immer Im Übrigen müsstest du, Rumpfi, auch mal sagen was du für Methoden kennst. Durch Primfaktorzerlegung von 2173 (falls gegeben) könnte man evtl noch was durch den CRS machen oder aber Square and Multiply könnte was bringen. Da du aber nichts darüber gesagt hast, WAS du schon kennst, kann man sich ja zwangsweise nur an deinen Weg halten
09.05.2009, 12:31	Rumpfi	Auf diesen Beitrag antworten »
Diese Methode funktioniert aber nicht bei folgender Rechnung: $\begin{eqnarray} 3^{2^{32}} mod 50 \end{eqnarray}$
09.05.2009, 12:36	AD	Auf diesen Beitrag antworten »
Nicht jede Methode ist für jeden Einsatzfall effizient. Bei sehr großen Exponenten (in Relation zum Modul) kommt zweckmäßig der (kleine) Satz von Fermat bzw. auch erweitert der Satz von Fermat-Euler zum Einsatz. Das trifft auf deine erste Aufgabe oben nicht zu, hier auf die zweite aber schon. Es gibt eben Werkzeuge für verschiedene Größenordnungen.
09.05.2009, 12:39	Rumpfi	Auf diesen Beitrag antworten »
In meinem Skriptum steht da, ich muss Phi(m) nehmen, nur was brauch ich für die berechnung von Phi(50)? Den Euklidischen Algorithmus oder was?
09.05.2009, 12:42	AD	Auf diesen Beitrag antworten »
Also ein wenig solltest du auch selbst tun, z.B. nachlesen, wie man $\begin{eqnarray} \varphi(n) \end{eqnarray}$ aus der Primfaktorzerlegung von $\begin{eqnarray} n \end{eqnarray}$ berechnet. Diesmal lasse ich das noch durchgehen: $\begin{eqnarray} \varphi(50) = \varphi(2\cdot 5^2) = (2-1)\cdot (5-1)5^1 = 20 \end{eqnarray}$ . EDIT: Du könntest aber genausogut doch den ersten Weg beschreiten, also ganz ohne Fermat-Euler. Mit etwas Nachdenken bleibt man da auch von übermäßiger Rechnerei verschont: Mit $\begin{eqnarray} a_n := 3^{2^n} \mod 50 \end{eqnarray}$ , d.h. Rekursion $\begin{eqnarray} a_n = a_{n-1}^2 \mod 50 \end{eqnarray}$ , kommt man über $\begin{eqnarray} a_0 &=& 3 \\ a_1 &=& 9 \\ a_2 &=& 31 \\ a_3 &=& 11 \\ a_4 &=& 21 \\ a_5 &=& 41 \\ a_6 &=& 31 \end{eqnarray}$ ziemlich schnell auf eine Periode der Länge 4, gültig ab Folgenglied $\begin{eqnarray} a_2 \end{eqnarray}$ . Damit ist $\begin{eqnarray} a_{32} = a_4 = 21 \end{eqnarray}$ .
09.05.2009, 13:13	Rumpfi	Auf diesen Beitrag antworten »
Wenn ich zusammenfassen darf, ich zerlege $\begin{eqnarray} 50 = 2^{1} 5^{2} \end{eqnarray}$ Dann muss ich diese Formel von Euler verwenden: $\begin{eqnarray} \varphi(m) = p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)... \end{eqnarray}$ Dabei ist 2^0 bereits 1.

Neue Frage »

Antworten »

Berechnung hoher Zahlen mit Modulo

Verwandte Themen