Körper, Ringe, Gruppen und RSA
Damit habe ich schon zweimal den Schwerpunktkurs Mathematik gestartet. Die Schüler erleben einen höheren Abstraktionsgrad als im Grundlagenfach, das Gebiet ist fast voraussetzungsfrei, und es ergeben sich bei der Einführung ins Programmieren aus dem Gebiet "Kryptologie" schöne Aufgaben mit steigendem Schwierigkeitsgrad.
Auslöser für die Entwicklung dieses Kurses war die Lektüre von Simon Singh, "Geheime Botschaften". Am Schluss muss jede Schülerin auf ihrem PC die Gratisversion des Programms "PGP" (ursprünglich von Phil Zimmerman) installieren, einen Satz Schlüssel erzeugen und mit mir verschlüsselt eine Botschaft austauschen.
Auch hier hat mein Freund Alfred Hepp wieder viele Stunden investiert, um die Skripte algebra_01, algebra_03, algebra_05 und algebra_06 sauber in LaTeX zu setzen. Dabei erfahren die Texte selber regelmässig noch deutliche Verbesserungen.
Kapitel 1 Körper Download: Algebra_01.pdf
Es wird axiomatisch definiert, welche Eigenschaften ein Zahlkörper haben muss, und die üblichen Konsequenzen aus den Axiomen werden gezogen. Es wird bewiesen, dass die Restklassen Zp genau dann einen Körper bilden, wenn p eine Primzahl ist.
Das Rechnen in Zp macht den Schülern oft Spass. Eine technische Herausforderung ist die effiziente Berechnung des multiplikativen Inversen in Zp. Der erweiterte euklidische Algorithmus wird in Excel, Delphi-Pascal und auf den TI-Rechnern implementiert: Download: Algebra_02.pdf
Kapitel 2 Ringe Download: Algebra_03.pdf
Die Definition eines Rings ist jetzt einfach, und etliche wichtige Beispiele sind schon bekannt: Z, Zn, Zn x Zm . Dann werden nxm-Matrizen über einem beliebigen Ring eingeführt, damit mit den quadratischen Matrizen auch ein relevantes Beispiel eines nicht-kommutativen Rings gegeben werden kann.
Auch hier stellt sich die Frage nach der Berechnung des multiplikativen Inversen. Als Antwort darauf wird der Gauss-Algorithmus besprochen, der auf den TI-Rechnern mit dem Befehl rref( ) implementiert ist.
Schliesslich können wir schon recht stark verschlüsseln mit invertierbaren Matrizen über Zp .
Download: Algebra_04.pdf
Kapitel 3 Gruppen Download: Algebra_05.pdf
Gestartet wird mit der Diëdergruppe D3, der Symmetriegruppe eines gleichseitigen Dreiecks. Der Begriff des "Isomorphismus" wird eingeführt, und es wird gezeigt, dass die Menge Pn aller Elemente in Zn, welche ein multiplikatives Inverses besitzen, eine Gruppe bilden. Das liefert reichlich Aufgaben für die Schüler.
Dann werden Untergruppen eingeführt sowie Sätze bewiesen wie zB dass die Ordnung einer Untergruppe ein Teiler der Gruppenordnung ist.
Ausflüge in das schöne Gebiet der kristallographischen Gruppen wären möglich.
Kapitel 4 RSA und PGP Download: Algebra_06.pdf
Das asymmetrische Verschlüsselungsverfahren von Rivest, Shamir und Adleman wird detailliert besprochen und bewiesen. Auch der Beitrag von Diffie und Hellmann wird gewürdigt, die schon 1976 gezeigt haben, dass es möglich ist, über öffentliche Kanäle einen geheimen Schlüssel zu vereinbaren - und worauf die Sicherheit dieses Verfahrens beruht. Schliesslich kommt noch Phil Zimmermann zum Zug, der all diese Ideen raffiniert gebündelt und der Öffentlichkeit gratis zur Verfügung gestellt hat.
Übungen und Klausuren samt Löungen
| m | Rechnen in Zn, Zahlkörper | Alg_K_Nov03.pdf |
||
| Ringe, Rechnen modulo p | Alg_K_Jan09.pdf | |||
| Körper, Ringe, Gruppen | Alg_K_Dez07.pdf | |||
| Gruppen, Übung 1 | Alg_U_Dez00.pdf | |||
| Gruppen, Übung 2 | Alg_U_Jan01.pdf | |||
| Körper, Ringe, Gruppen | Alg_K_Sept03.pdf | |||
| Gruppen, RSA | Alg_K_April08.pdf | |||
| Gruppentheorie und RSA | Alg_K_Mai09.pdf |