Eine kanonische Form zur Darstellung äquivalenter Codes : Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie

Es sei G eine beliebige Gruppe, welche auf einer Menge X operiere. Wir nennen eine Abbildung CF von X nach X eine Kanonisierung, falls sie jedem Element x in X einen eindeutigen Repräsentanten (die kanonische Form) CF(x) derselben Bahn Gx zuordnet. Die Entscheidung, ob zwei gegebene Objekte x, y in X äquivalent sind, d.h. der gleichen Bahn angehören, erweist sich häufig als schwierig zu entscheidendes Problem. Oft ist für diese Probleme kein Algorithmus bekannt, welcher in der Lage ist, die Fragestellung für alle Eingaben in Polynomialzeit zu beantworten. Ein prominentes Beispiel ist die Isomorphie von Graphen. Eine Kanonisierung bietet nicht nur eine elegante Lösung für die obige Fragestellung, sondern bereitet auch die Möglichkeit, Datenbanken der Objekte aus X bis auf Isomorphie aufzubauen und mit diesen in der Praxis sinnvoll zu arbeiten. Hier ist es entscheidend, dass sich diese mathematische Funktion CF auch aus algorithmischen Gesichtspunkten effizient umsetzen lässt. Dies gilt insbesondere dann, wenn kein polynomielles Laufzeitverhalten zu erzielen ist. In dieser Dissertation werden nun Gruppenoperationen behandelt, welche in der Codierungstheorie, Kryptographie und Geometrie auftreten. Zunächst wird das bekannte Verfahren, über Partitionen und Verfeinerungen endliche Graphen zu kanonisieren auf beliebige Gruppenoperationen, verallgemeinert. Da in der Codierungstheorie häufig ein semidirektes Produkt einer Gruppe G und einer symmetrischen Gruppe S_n auf einer Menge X^n operiert, wird für diesen Spezialfall ein maßgeschneidertes Vorgehen entwickelt. Das Hauptaugenmerk der Arbeit bildet die Bereitstellung eines effizienten Algorithmus zur Kanonisierung linearer Codes über einem beliebigen endlichen Kettenring R. Die Gruppenoperation ist hierbei über die Operation der Gruppe aller semimonomialen Transformationen des Umgebungsraums R^n gegeben. Es wird im Detail ausgeführt, wie sich ein solcher Kanonisierungsalgorithmus bis hin zur Implementierung umsetzen lässt. Der vorgestellte Algorithmus arbeitet mit exponentiellen Zeitaufwand. Dieses Vorgehen wird im Sinne der Komplexitätstheorie durch den Beweis der Aussage, dass das Äquivalenzproblem für lineare Codes mindestens so schwer wie das Isomorphieproblem für Graphen ist, gerechtfertigt. Die Arbeit schließt mit verschiedenen Modifikationen an dem Kanonisierungsalgorithmus, um auch weitere, ähnliche Problemstellungen innerhalb und außerhalb der Codierungstheorie zu bearbeiten. Insbesondere wird hier, anhand vieler konkreter Beispiele, aufgezeigt, dass man über einen effizienten Kanonisierungsalgorithmus stets in die Lage versetzt wird, ein Repräsentantensystem der Äquivalenzklassen auf X, beziehungsweise einer G-invarianten Teilmengen Y von X, zu berechnen. Hierüber werden schließlich auch Nichtexistenzaussagen mit Hilfe des Computers bewiesen.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bayreuth

Year

2013

Author dc:creator

• Feulner, Thomas

Contributors dc:contributor

• Kerber, Adalbert

Repository record source_url

https://epub.uni-bayreuth.de/id/eprint/42/

OAI identifier oai:identifier

oai:epub.uni-bayreuth.de:42