i

Station - Modulare Potenz

Potenzbildung modulo einer vorgegebenen Zahl

Vorgegeben sei eine natürliche Zahl n. Eine natürliche Zahl a wird mit einer natürlichen Zahl x modulo n potenziert, indem man sie mit x potenziert und anschließend von der Potenz den Rest bei der Division durch n berechnet. Das Ergebnis ist also [ax]%n. Beachte, dass das Ergebnis bei der Potenzbildung modulo n immer eine Zahl kleiner als n ist.

Aufgabe 1

(a) Berechne [84]%5. Berechne auch [([([([8]%5)*8]%5)*8]%5)*8]%5. Was stellst du fest?

(b) Welche Vorteile ergeben sich bei großen Zahlen, wenn man [ax]%n wie folgt berechnet:[(...([([a]%n)*a]%n)...)*a]%n

Aufgabe 2

Berechne [a(p-1)]%p für verschiedene natürliche Zahlen a und verschiedene Primzahlen p. Für welche Zahlen erhält man als Ergebnis 1?

p = 23
a = 42
print( a**(p-1)%p )

Satz (Kleiner Fermatscher Satz)

Sei p eine Primzahl und a eine natürliche Zahl, die kein Vielfaches von p ist. Dann gilt

[a(p-1)]%p = 1

Die Aussage dieses Satzes ist nicht offensichtlich. Eine vollständige Begründung kann hier auch nicht geliefert werden. Die folgenden Überlegungen sollen den Zusammenhang zumindest in Teilen begründen.

Gegeben sei eine Primzahl p und eine natürliche Zahl, die kein Vielfaches von p ist (z.B. p=5 und a = 12). Wenn man [1*a]%p, [2*a]%p, [3*a]%p, ..., [(p-1)*a]%p berechnet, so erhält man als Ergebnisse die Zahlen 1, 2, 3, ..., p-1 - allerdings in anderer Reihenfolge. Probiere das selbst einmal mit den gegebenen Zahlen (und auch anderen) aus.

Hieraus lässt sich mit einigen Rechengesetzen folgender Zusammenhang herleiten:

[(1*a)*(2*a)*(3*a)*...*((p-1)*a)]%p = [1*2*3*...*(p-1)]%p

Umgeformt erhält man:

[1*2*3*...*(p-1)*a(p-1)]%p = [1*2*3*...*(p-1)]%p

Mit einigen zusätzlichen Überlegungen kann man jetzt schließen:

[a(p-1)]%p = 1

Suche

v
11.4.2.5
inf-schule.de/kryptologie/rsa/modrechnen/station_modpotenz
inf-schule.de/11.4.2.5
inf-schule.de/@/page/Ju5yqE5VSuL1uxmX

Rückmeldung geben