Fachrichtung/Institution: Informatik

Projektleitung: Prof. Dr. Johannes Buchmann

Forschungsschwerpunkt(e) des Projektes:

Das Projekt besteht aus folgenden Teilen:
- Algorithmen zur Faktorisierung großer natürlicher Zahlen
- Komplexität und Effizienz von Algorithmen zur Berechnung von Invarianten algebraischer Zahlkörper.
- Berechnung der Punktanzahl auf einer elliptischen Kurve über einem endlichen Körper.
- Eine C++ Klassenbibliothek für die Computeralgebra.

Wesentliche Publikationen:

I. Biehl, J. Buchmann, Algorithms for quadratic orders. In: Proceedings Symposium on Applied Mathematics, Vol. 48, American Mathematical Society, 425-450, 1994.
F. Lehmann, M. Maurer, V. Müller, V. Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three. Proceedings of ANTS I, LNCS 877, 60-70, 1994.)

Beteiligte Forscher/innen:

Johannes Buchmann, Dr. rer. nat. , Prof. ; Franz-Dieter Berger, Stipendiat der Siemens AG; Ingrid Biehl, Dr. rer. nat., wissenschaftliche Mitarbeiterin; Thomas Denny, wissenschaftlicher Mitarbeiter (DFG); Christine Hollinger, Stipendiatin des Graduiertenkollegs; Volker Müller, wissenschaftlicher Mitarbeiter; Thomas Papanikolaou, wissenschaftlicher Mitarbeiter (DFG); Ralf Roth, wissenschaftlicher Mitarbeiter (SFB); Victor Shoup, Ph. D. Stipendiat der Alexander von Humboldt-Stiftung; Oliver van Sprang, Dr. rer. nat., wissenschaftlicher Mitarbeiter (DFG); Christoph Thiel, Stipendiat des Graduiertenkollegs; Damian Weber, Doktorand; Jörg Zayer, wissenschaftlicher Mitarbeiter (DFG); Thilo Zieschang, Stipendiat des Graduiertenkollegs

Zahl der Wissenschaftler/innen, die in den letzten 24 Monaten mitgearbeitet haben: 14

davon

Drittmittelförderung:

Deutsche Forschungsgemeinschaft (DFG), Siemens AG

Projektbeschreibung:

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.