Komplexität und Effizienz von Algorithmen in der Zahlentheorie

Abstract

Das Projekt besteht aus den vier genannten Forschungsschwerpunkten: Die Schwierigkeit des Problems, große natürliche Zahlen in ihre Primfaktoren zu zerlegen, ist die Grundlage des bedeutenden RSA-Kryptosystems. Ziel dieses Teils des Projekts waren verteilte Implementierungen von state of the art Algorithmen, die mit den weltbesten Implementierungen konkurrieren können. Die Gruppe nimmt regelmäßig erfolgreich am RSA-Faktorisierungswettbewerb teil. Zu den wichtigsten algorithmischen Problemen der algebraischen Zahlentheorie gehören die Bestimmung der Klassenzahl und Klassengruppe eines algebraischen Zahlkörpers, die Bestimmung seiner Einheitengruppe und seines Regulators und die Lösung von Normgleichungen. In diesem Teil des Projekts wurden unter anderem folgende Beiträge geleistet. Es wurde ein neuer Algorithmus zur Berechung der Klassengruppe eines beliebigen algebraischen Zahlkörpers entwickelt, implementiert und experimentell untersucht. Ferner wurde eine neue Darstellung von Elementen algebraischer Zahlkörper entdeckt, die es erlaubt zu zeigen, daß die Berechnung von Klassenzahl und Regulator von Zahlkörpern und die Lösung von Normgleichungen in Zahlkörpern zur Komplexitätsklasse NP gehört. Um die Sicherheit von Public- Key- Kryptosystemen basierend auf elliptischen Kurven zu ermitteln, ist es wichtig, die Punktanzahl der zugrundeliegenden elliptischen Kurve zu berechnen. Es wurde ein Algorithmus für große endliche Primkörper implementiert, der erfolgreich angewendet wird. Aus der Fülle der in den letzten Jahren entstandenen Software entstand eine C++ Klassenbibliothek, die alle Interessierten verwenden können.