Lektion Fermat/Ordnung/Erzeuger

Anleitung zum Selbstudium

• starten Sie bei Folie 1 des Foliensatzes, rechnen Sie den dort skizzierten Diffie-Hellman-Schlüsselaustausch nach
• Folie 2: das Kongruenzzeichen wird eingeführt (ein = mit drei Strichen)
• lesen Sie hierzu den Wiki-Eintrag Modulare Arithmetik
• versuchen Sie, die Division 1/b mod n zu verstehen (Folien 3-5)
• Folie 5 führt dies am Beispiel 1/19 mod 23 vor
• hierzu muss man den Euklidischen Algorithmus einmal "vorwärts" und einmal "rückwärts" ausführen (= erweiterter Euklid)
• vorwärts: wenn Ihnen der Algorithmus aus früheren Vorlesungen nicht (mehr) präsent ist, schauen Sie in Wiki Euclidean Algorithm
• rückwärts: die Gleichungen werden umgestellt und nacheinander der Rest durch die jeweils linke Seite ersetzt
• nach der letzten Ersetzung hat man eine Gleichung in n und b: es ist x*b+y*n=1
• daher ist x mod n das Inverse zu b, oder x = 1/b mod n
• Divisionsaufgaben a/b schreibt man als a*(1/b) mod n, wobei für 1/b der erweiterte Euklid benutzt wird
• für kleine n ist das Ausprobieren schneller als der erweiterte Euklid (Folie 7)
• Folie 8+9: effizientes Potenzieren, detailliertere Fassung etwa unter math.stackexchange
• Folie 10: hier fällt der Begriff Ordnung mod p, eine Definition findet man hier: Wiki: multiplicative order
• Folie 11: enthält für alle Elemente die Ordnungen mod 7
• Folie 13: der (kleine) Satz des Fermat ist zentral für die Kryptographie, seine Verallgemeinerung erklärt das RSA-Verfahren, in der Originalversion ist er Basis für Primzahltests
• Folie 14: Programmieren Sie! In ihrer Lieblingsprogrammiersprache! Wer unentschlossen ist, dem sei Python empfohlen, sehr praktisch, um schnell Experimente mit Public-Key-Kryptographie zu durchzuführen. Rechnen Sie Potenzen mod n aus. Finden Sie damit Beispiele zum Verstehen des Fermat'schen Satzes, damit meine ich Nichtprimzahlen n und ganze Zahlen a, für die a^(n-1) mod n nicht gleich 1 ist.
• warum sind die erwähnten Beispiele keine Gegenbeispiele des Fermat'schen Satzes?
• Antwort: dieser sagt nur "n Primzahl" => "a^(n-1) = 1 mod n" und nicht das Umgekehrte
• Umgekehrt gilt nur als Kontraposition: "a^(n-1) != 1 mod n" => "n nicht Primzahl"
• dies wird in der Kryptographie benutzt, um Nichtprimzahlen auszuschließen
• die Expertenversion dieses Tests ist der Miller-Rabin-Primzahltest Miller-Rabin