Diploma Thesis DIP-2330

BibliographyStaiger, Stefan: Ring-Isomorphie-Probleme und das Faktorisieren großer Zahlen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2330 (2005).
123 pages, german.
CR-SchemaF.1.3 (Complexity Measures and Classes)
F.2.1 (Numerical Algorithms and Problems)
KeywordsRinge; Algebra; Komplexitätstheorie; Faktorisieren; Automorphismen; Isomorphismen; Graph-Isomorphie; Zahlentheorie; Polynome; Arthur-Merlin-Protokolle
Abstract

Die Diplomarbeit ist eine Ausarbeitung und Weiterführung der aktuellen Forschung von Neeraj Kayal und Nitin Saxena. Diese haben das algorithmische Studium von Fragen rund um Ringe begonnen. Die Diplomarbeit präsentiert die hierbei entstandenen Algorithmen und komplexitätstheoretischen Überlegungen in ausführlicher und verständlicher Weise. Behandelt werden beispielsweise die Fragen, ob zwei Ringe isomorph sind, wie viele Automorphismen sie haben und wie man Iso- und Automorphismen berechnen kann. Hierzu werden eine Reihe mathematischer Grundlagen erläutert.

Darüber hinaus leitet die Diplomarbeit neue Ergebnisse zu endlichen Ringen her und korrigiert einen Fehler von Kayal und Saxena. Ferner werden die Ring-Probleme in Beziehung gesetzt zu den bekannten Problemen der Graph-Isomorphie und des Faktorisierens großer Zahlen. Die Arbeit präsentiert außerdem einen Überblick über die aktuellen Faktorisierungsverfahren und schließt mit einer Reihe noch offener Fragen, die als Grundlage für weitere Forschung dienen können.

Englisch:

The diploma thesis presents and continues the current research of Neeraj Kayal and Nitin Saxena. They started studying algorithmic problems around rings. The diploma thesis presents the algorithms and insights achieved in a detailed and understandable manner. For example, topics like counting ring iso- and automorphisms and the ring isomorphism problem are covered. For that, we explain the mathematical basics needed to understand the ideas.

Furthermore, the diploma thesis proofs new results for finite rings and corrects an error of Kayal and Saxena. Also, some connections between the ring problems and the well-known problems of graph isomorphism and factoring large numbers are shown. The work gives an overview of the algorithms currently used for factoring numbers and presents some open questions that might be used as a starting point for future research.

Full text and
other links
PDF (1041025 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Copyright2005 by Stefan Staiger
ContactStefan Staiger stefan.staiger@gmx.net
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateFebruary 7, 2006
   Publ. Computer Science