Special Linear Systems on Curves and Algorithmic Applications

Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar. In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden. Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts. Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten. Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet