Dozent:

Dr. R. Carls

Veranstaltungsform:

Vorlesung V3
Übung Ü1

Ort und Termin:

Die Vorlesung und die Übung finden auf wöchentlicher Basis statt (erste Vorlesung am 15.4.2008).

Vorlesung:	Dienstag 10-12 Uhr	He 18 Raum E60
	Donnerstag 10-11 Uhr	He 18 Raum E60
Übung:	Donnerstag 11-12 Uhr	He 18 Raum E60

Voraussetzungen:

Die Vorlesung richtet sich an Studenten der Mathematik und Informatik im Hauptstudium. Lehramt-, Diplom-, Bachelor- und Master-Studenten sind gleichermassen angesprochen. Kenntnisse der Algebra sind hilfreich, werden aber nicht vorausgesetzt. Ein gleichzeitiger Besuch der von Prof. I. I. Bouw angebotenen Veranstaltung Elementare Zahlentheorie bietet sich an.

Inhalt:

Es sollen in erster Linie Algorithmen diskutiert werden, die eine Anwendung in der mathematischen Kryptographie haben. Es wird darauf geachtet, dass es so gut wie keine Überschneidung mit der im Fachbereich Informatik angebotenen Vorlesung Kryptographie gibt. Zentrale Themen bilden die den RSA- und ElGamal-Kryptosystemen zugrunde liegenden zahlentheoretischen Probleme. Die Sicherheit des populären RSA-Kryptosystems basiert auf der Schwierigkeit des Faktorisierens von natürlichen Zahlen. Das Problem der Berechnung von diskreten Logarithmen in endlichen Körpern liegt dem ebenfalls weit verbreiteten ElGamal-Kryptosystem zugrunde. Wir werden die bestehenden Methoden zum Faktorisieren von natürlichen Zahlen und Berechnen von diskreten Logarithmen vorstellen und deren Komplexität analysieren. Ausserdem sollen Primzahl-Tests besprochen werden, d.h. Algorithmen zur Entscheidung der Primheit einer gegebenen natürlichen Zahl. Eine Auswahl der in der Vorlesung zu besprechenden Algorithmen soll im Rahmen des Praktikums implementiert werden.

Scheinkriterien:

Ein Scheinerwerb ist vorgesehen. Für Lehramts- und Diplom-Studenten reichen 50 Prozent der im Praktikum erreichbaren Punkte aus, um den Schein zu erlangen.Für Bachelor- und Master-Studenten ist eine zusätzliche mündliche Prüfung vorgesehen. Zulassungsvoraussetzung für die mündliche Prüfung sind 50 Prozent der im Praktikum erreichbaren Punkte. Für die mündliche Prüfung muss man sich noch vor Vorlesungsbeginn beim Dozenten anmelden.

Praktikum:

Das Praktikum umfasst Programmieraufgaben, die in der Sprache PARI/GP gelöst werden sollen. Die Praktikumsaufgaben werden im 2-Wochen-Zyklus ausgegeben. Die Sprache GP ist auf dem Server turing der Fakultät Mathematik und Wirtschaftswissenschaften vorinstalliert. Der GP-Interpreter lässt sich mittels des Befehls gp starten. Die Dokumentation des PARI/GP Systems ist abrufbar durch Eintippen des Kommandos gphelp. Das Computer Algebra System PARI/GP ist versehen mit einer GNU public license und ist frei erhältlich auf der Seite des PARI/GP Projektes.

Literatur:

D. Bressoud, Factorization and primality testing, Springer, 1989
O. Forster, Algorithmische Zahlentheorie, Vieweg, 1996
R. Crandall, C. Pomerance, Prime numbers, a computational perspective. Springer, 2003

Weitere Literatur ist zu finden im Semesterapparat des Dozenten in der Mathematik-Bibliothek in der Helmholtzstrasse 18.

Weitere Informationen:

<link fileadmin website_uni_ulm mawi.inst.100 vorlesungen ss08 algorithmen algo_info.pdf download>Offizielle Ankündigung