Große Zahlen modulo rechnen? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:18 So 16.12.2007 | | Autor: | Torboe |
| Aufgabe | Berechne:
17^302 mod 101 |
Hi!
Ich weiß, dass es irgendwie mit dem Satz von Fermat geht, aber ich hab außer ein paar kläglichen Versuchen bis jetzt echt noch keine vernünftigen Lösungsversuche parat.
Wie rechne ich allg. große Zahlen modulo? Selbst wenn ich ne Zahl hab, die der Taschenrechner noch frisst, funktioniert ja das übliche Prinzip der Modulorechnung irgendwie nicht mehr.
Vielen Dank schonmal im voraus!
gruß torboe
|
|
| |
|
Hallo Torboe,
solche Potenzen berechnet man am besten mit dem sogenannten "Square and Multiply" Algorithmus. Dazu wandelt du den Exponenten in eine Binärzahl um, genauer gesagt, du schreibst ihn als Summe von Zweierpotenzen. Dann nutzt du die Potenzgesetze aus: [mm] x^{a b} [/mm] = [mm] x^a x^b. [/mm] Du machst also eine Tabelle mit allen Zweierpotenzen als Exponent, bis zum größten den du brauchst. Bei der Berechnung kannst du natürlich schon jedes Mal reduzieren, so bleiben die Zahlen übersichtlich. Wenn du deine Tabelle fertig hast, musst du nur noch zusammenmultiplizieren!
Ein kleines Beispiel: 3^12 mod 11
12 = [mm] 2^3 [/mm] + [mm] 2^2, [/mm] also berechnest du [mm] 3^{2^0}, 3^{2^1}, 3^{2^2} [/mm] und [mm] 3^{2^3} [/mm] mod 11
3^12 ist dann [mm] 3^{2^2} 3^{2^3}
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:39 So 16.12.2007 | | Autor: | Torboe |
Danke erstmal für die schnelle Antwort :)! Aber mir ist da noch so manches unklar. Bist du dir sicher, dass dieses Potenzgesetz so stimmt??
$ [mm] x^{a b} [/mm] $ = $ [mm] x^a x^b. [/mm] $
Ich dachte immer, es gilt:
EDIT: [mm] x^a [/mm] * [mm] x^b [/mm] = x^(a+b)
Und warum ist 3^12 = $ [mm] 3^{2^2} 3^{2^3} [/mm] $ ??
3^12 ist bei mir 531441 und $ [mm] 3^{2^2} 3^{2^3} [/mm] $ = 59049
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:41 So 16.12.2007 | | Autor: | Torboe |
editiert
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:18 So 16.12.2007 | | Autor: | rainerS |
Hallo!
Die Klammern sind falsch gesetzt; du hast [mm]3^{2^3}=(3^2)^3[/mm] gerechnet, gemeint ist [mm] 3^{12} = 3^{(2^2)}* 3^{(2^3)} [/mm]. Lies dir die Rechnung nochmal genau durch.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:38 So 16.12.2007 | | Autor: | Torboe |
ok, also bei kleinen Zahlen funktioniert das ganze. aber bei riesigen zahlen gehts irgendwie nicht, da ja der taschenrechner das nicht mehr so genau bis auf kommastellen rechnen kann.
was mach ich dann??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:01 So 16.12.2007 | | Autor: | rainerS |
Hallo!
> ok, also bei kleinen Zahlen funktioniert das ganze. aber
> bei riesigen zahlen gehts irgendwie nicht, da ja der
> taschenrechner das nicht mehr so genau bis auf kommastellen
> rechnen kann.
> was mach ich dann??
Du hast eine Kleinigkeit in madde_dongs Antwort überlesen, die nur so ganz nebenbei auftaucht:
(EDIT: fehlerhafte Multiplikation korrigiert)
Du rechnest jede einzelne Multiplikation modulo 101:
[mm] 17^{302} \bmod 101 = (17^2)^151 \bmod 101 = (17^2 \bmod 101 )^{151} \bmod 101 = (289\bmod 101)^{151}\bmod 101 = 87^{151} \bmod 101 =[/mm]
[mm] = 87 * 87^{150} \bmod 101 = 87 * 7569^{75} \bmod 101 = 87 * (7569 \bmod 101)^{75} \bmod 101 = 87 * 95^{75} \bmod 101[/mm]
[mm] = 87 * 95 * 95^{74} \bmod 101 = ((87*95)\bmod 101 * 95^{74})\bmod 101 = 84* 95^{74} \bmod 101 [/mm]
usw.
Das ist die Grundidee des Square-and-Multiply: bei ungerade Exponenten einen Faktor abspalten, bei geraden die Basis quadrieren und den Exponenten halbieren.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:25 So 16.12.2007 | | Autor: | Torboe |
ok vielen dank, vielen dank rainers!
jetzt hab ichs glaub fast. ich hab mir die rechnungen bestimmt schon 100x durchgelesen. braucht wohl etwas, bis sich das im kopf gesetzt hat ;)
eine kurze frage hab ich noch: wie du das mit den geraden exponenten gemacht hast, ist mir klar. aber bei den ungeraden nicht. also wie du auf die 26^151 mod 101 kommst zb.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:33 So 16.12.2007 | | Autor: | rainerS |
Hallo!
> ok vielen dank, vielen dank rainers!
> jetzt hab ichs glaub fast. ich hab mir die rechnungen
> bestimmt schon 100x durchgelesen. braucht wohl etwas, bis
> sich das im kopf gesetzt hat ;)
> eine kurze frage hab ich noch: wie du das mit den geraden
> exponenten gemacht hast, ist mir klar. aber bei den
> ungeraden nicht. also wie du auf die 26^151 mod 101 kommst
Nach jeder Multiplikation die mod-Operation: zum Beispiel: [mm](26^2)\bmod 101 = 676 \bmod 101 = 70[/mm].
Aber ich sehe gerade, dass ich mich bei der [mm]17^2[/mm] verrechnet habe... ich korrigiere es gleich.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:41 So 16.12.2007 | | Autor: | Torboe |
muchos gracias rainers und auch madde_dong!
habs jetzt durchgerechnet und es funktioniert.
vielen dank!
|
|
|
|
