SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

ResearchPaper zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-364
URL: http://scidok.sulb.uni-saarland.de/volltexte/2001/36/


Komplexität und Effizienz von Algorithmen in der Zahlentheorie

Buchmann, Johannes ; Berger, Franz-Dieter

html-Format:
Dokument1.html

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Algorithmus , Zahlentheorie
Freie Schlagwörter (Deutsch): Klassenbibliothek
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Sprache: Deutsch
Erstellungsjahr: 1994
Publikationsdatum: 15.05.2001
Kurzfassung auf Deutsch: 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.

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English