Mathematik HTL 4/5, Schulbuch

269 7.1 Kryptographie Mit p bezeichnen wir eine Primzahl und mit a eine positive natürliche Zahl, die nicht von p geteilt wird. Dann ist der Rest von a p – 1 nach Division mit Rest durch p gleich 1. In Kurzschreibweise: ( a p – 1 ) mod p = 1 Multipliziert man auf beiden Seiten des Gleichheitszeichens mit a mod p, erhält man ( a p ) mod p = a mod p und das ist für natürlichen Zahlen a richtig. Diesen Satz kann man benutzen, um Reste von Potenzen nach Division mit Rest durch Prim- zahlen noch schneller zu berechnen. 1039 Berechne den Rest von 23 34567 nach Division mit Rest durch 13. Wir verwenden zur Berechnung dieser Potenz, dass nach dem Kleinen Satz von Fermat gilt: (23 12 ) mod 13 = 1. Wir dividieren zuerst 34567 mit Rest durch 12(= 13 – 1): 34567 = 2880·12 + 7 Also ist 23 34567 = (23 12 ) 2880 ·23 7 und (23 34567 ) mod 13 = ((23 12 mod 13) 2880 (23 7 mod 13)) mod 13 = = ((1 2880 mod 13)(23 7 mod 13)) mod 13 = 23 7 mod 13 = = (23 mod 13) 7 mod 13 = (10 mod 13) 7 mod 13 = = ((100 mod 13) 3 (10 mod 13)) mod 13 = ((9 mod 13) 3 (10 mod 13)) mod 13 = = ((729 mod 13)(10 mod 13)) mod 13 = (1·10) mod 13 = 10. Der Rest von 23 34567 nach Division mit Rest durch 13 ist 10. 1040 Berechne die Reste der Potenz a n nach Division mit Rest durch die Primzahl p. a. a = 2, n = 10000, p = 23 c. a = 10, n = 10000, p = 59 b. a = 2, n = 17306, p = 41 d. a = 37, n = 90341, p = 101 1041 Erstelle eine Wertetabelle für die Funktion Z k ¥ Z p , n ¦ a n mod p, für die gegebenen Zahlen k, p und a. Benutze dabei, dass (a n + 1 ) mod p = ((a mod p)((a n ) mod p)) mod p ist. a. k = 12, p = 7, a = 4 b. k = 12, p = 7, a = 5 c. k = 15, p = 11, a = 7 1042 Finde positive natürliche Zahlen a und q so, dass (a q – 1 ) mod q nicht 1 ist. 1043 Gegeben sind eine Primzahl p, eine natürliche Zahl n mit ggT(n, p – 1) = 1 und eine natürliche Zahl b, die kleiner als p ist. Berechne eine „n-te Wurzel aus b modulo p“, das heißt, eine natürli- che Zahl a < p mit der Eigenschaft (a n ) mod p = b. Berechne anschließend die 7. Wurzel aus 100 modulo 541. Wir berechnen mit dem erweiterten euklidischen Algorithmus ganze Zahlen u, v mit 1 = ggT(n, p – 1) = u·n + v·(p – 1) und u > 0, v < 0. Die Zahl a = (b u ) mod p < p hat dann die gewünschten Eigenschaften. Denn: ((b u ) mod p) n = (b n·u ) mod p = (b 1 – v·(p – 1) ) mod p = (b mod p)((b (‒v)·(p – 1) ) mod p) mod p = = ((b mod p)((b p – 1 ) -v mod p)) mod p = (b mod p)(1mod p) = b mod p = b. Für p = 541 und n = 7 und b = 100 erhalten wir 463·7 – 6·540 = 1, also u = 463 und a = 100 463 mod 541 = 164. Daher ist (164 7 )mod 541 = 100. Also: „Die 7. Wurzel aus 100modulo 541 ist 164“. 1044 Berechne zu jeder natürlichen Zahl b, die kleiner als 11 ist, eine natürliche Zahl a < 11 mit (a 3 ) mod 11 = b. Kleiner Satz von Fermat B Reste von Potenzen schnell berechnen mcd i9gh99 B B B Wurzelziehen durch Potenzieren B B Nur zu Prüfzwecken – Eigentum des Verlags öbv