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

Titelangaben

Feulner, Thomas:
Eine kanonische Form zur Darstellung äquivalenter Codes : Computergestützte Berechnung und ihre Anwendung in der Codierungstheorie, Kryptographie und Geometrie.
Bayreuth , 2014 . - IX, 176 S.
( Dissertation, 2013 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Weitere URLs

Angaben zu Projekten

Abstract

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.

Abstract in weiterer Sprache

Let G be some arbitrary group acting on an arbitrary set X. We call a function CF from X to X canonization, if it maps each element x in X to some unique representative (canonical form) CF(x) of the same orbit Gx.

Very often it is hard to decide, if two given objects x, y in X are equivalent, i.e. lie in the same orbit. In many cases, we do not know an algorithm, which is able to solve this problem for all instances in polynomial time. A very prominent example is the graph isomorphism problem.

The canonization of objects does not only offer an elegant way of answering the above question. It does also provide the possibility to set up a computerised database for practical application. At this point, it is very important that this mathematical function CF allows an efficient algorithmic implementation. This is particularly true, if we can not expect a polynomial time behavior.

In this thesis, we investigate group actions, which naturally appear in coding theory, cryptography and geometry. In a first step, the well-known approach to use partitions and refinements to formulate a canonization algorithm for finite graphs is generalized to cope with arbitrary group actions. In coding theory, we will often find the situation that there is a semidirect product of a group G and the symmetric group S_n acting on a set X^n . Therefore we will give a tailored approach to this particular group action.

The main focus is placed on the development of an efficient algorithm for the canonization of linear codes over some arbitrary finite chain ring R. In this case, the group action is given by the action of the group of semimonomial transformations of the ambient space R^n . It is shown in detail, how to achieve such an algorithm and how to implement it in practice. The developed algorithm works in exponential time. From the point of view of complexity theory, this approach is justified by proving a lemma, which states, that the equivalence problem for linear codes is at least as hard as the graph isomorphism problem.

Finally, the thesis presents different modifications to the canonization algorithm to work on similar problems within and outside of coding theory. In particular, we give many concrete examples which show, that an efficient canonization algorithm enables us to compute a transversal of the equivalence classes of X or of a G-invariant subset Y of X. In some cases, these results do lead to nonexistence proofs by computer, as well.