Hohe Potenzen Modulo rechnen < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:31 So 16.11.2014 | | Autor: | pauly |
| Aufgabe | | Berechne 647^689 mod 689 |
Hallo liebe Community!
Kann mir einer bei dieser Aufgabe weiterhelfen?
Wie kann ich die oben genannte Rechnung am "einfachsten" berechnen?
Mit z.B. 20^11 mod 689 hab ich kein Problem..
aber 647^689 mod 689 sind schon enorme Zahlen. Diese dann aufzuteilen, würde doch ewig dauern. Kann mir einer bitte einen Tipp geben.
Also für 20^11 mod 689, hab ich das so gelöst:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
20^11 = 20 * [mm] (20^2)^5 [/mm]
= 20 [mm] *(400)^5
[/mm]
= [mm] 20*400(400^2)^2
[/mm]
=421 * [mm] 152^2
[/mm]
=421 * 367
=171 also is der Rest 171
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:43 So 16.11.2014 | | Autor: | Teufel |
Hi!
Du kannst im Exponenten modulo [mm] \varphi(689) [/mm] rechnen, wobei [mm] \varphi [/mm] die Eulersche Phifunktion ist. Ist dir das geläufig? Dann ist der Exponent wieder kleiner.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:56 So 16.11.2014 | | Autor: | abakus |
Hallo,
du kannst auch 689 in Primfaktoren zerlegen (53*13) und mit simultanen Kongruenzen mod 53 und mod 13 arbeiten.
Dabei kann der kleine Fermat hilfreich sein.
|
|
|
|
