7 hoch 100 module 13?

... komplette Frage anzeigen

1 Antwort

Weg 1: Es gibt ein Gesetz:

wenn ggT(a,m)=1 {wie hier, da 7 und 13 Primzahlen}, dann gilt:
a^k mod m = a^(k mod CarmichaelLambda[m]) mod m

CarmichaelLambda für Primzahlen ist 1 kleiner, also

7^100 mod 13

= 7^(100 mod 12) mod 13

= 7^4 mod 13

= 2401 mod 13

= 9

Weg 2: 9 ^25 mod 13

= 9^(25 mod 12) mod 13

= 9^1 mod 13 = 9 mod 13 = 9

Weg 3: pow-Mod -Algorithmus

http://www.lamprechts.de/gerd/Roemisch_JAVA.htm

Beispiel 122 ergibt mit aB[0]=a=7;b=100;c=13; nach wenigen Schritten auch 

9

Kontrolle mit 
http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

stimmt wie im Bild zu sehen

P.S.: es gibt dort sogar PowPow-Mod für Potenztürme!

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?