Refine
Document Type
- Doctoral Thesis (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- Gröbner-Basis (3) (remove)
Eine Gruppe erfüllt die Tits-Alternative, wenn sie entweder eine nicht-abelsche freie Untergruppe vom Rang 2 enthält oder virtuell auflösbar ist, d. h. eine auflösbare Untergruppe von endlichem Index enthält. Diese Eigenschaft geht auf J. Tits zurück, der sie für endlich erzeugte lineare Gruppen nachwies. Es wird eine relevante Klasse endlich präsentierter Gruppen in Bezug auf die Tits-Alternative untersucht. Die betrachteten Gruppen stellen eine Verallgemeinerung von Pride-Gruppen und der von Vinberg betrachteten Gruppen erzeugt von periodisch gepaarten Relationen für drei Erzeugende dar. Zusätzlich treten diese Gruppen als Fundamentalgruppen hyperbolischer Orbifaltigkeiten auf. Es wird der Nachweis der Tits-Alternative unter bestimmten Voraussetzungen an die Präsentierungen der betrachteten Gruppen erbracht. Für diesen Nachweis werden verschiedene Methoden angewandt: Es werden zum einen homomorphe Bilder der Gruppen betrachtet. Zum anderen wird die Existenz wesentlicher Darstellungen in eine lineare Gruppe nachgewiesen. Basierend auf diesen Darstellungen kann in vielen Fällen der Nachweis der Existenz nicht-abelscher freier Untergruppen erbracht werden. Zusätzlich wird für den Nachweis der Endlichkeit und damit der Tits-Alternative einiger Gruppen eine Methode angewandt, die auf Berechnungen von Gröbner-Basen in nicht-kommutativen Polynomringen basiert. Es wird dabei die Dimension der Gruppenringe betrachtet als Vektorräume berechnet. Für die betrachtete Klasse von Gruppen wird für Relationen der Blocklänge 1 die Tits-Alternative vollständig nachgewiesen. Als Folgerung ergibt sich eine Klassifikation der endlichen unter diesen Gruppen.
Commutative Gröbner bases have a lot of applications in theory and practice, because they have many nice properties, they are computable, and there exist many efficient improvements of their computations. Non-commutative Gröbner bases also have many useful properties. However, applications of non-commutative Gröbner bases are rarely considered due to high complexity of computations. The purpose of this study was to improve the computation of non-commutative Gröbner bases and investigate the applications of non-commutative Gröbner bases. Gröbner basis theory in free monoid rings was carefully revised and Gröbner bases were precisely characterized in great detail. For the computations of Gröbner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-Möller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gröbner basis theory in free bimodules over free monoid rings. The Buchberger Procedure was also formulated and improved in this setting. Moreover, J.-C. Faugere's F4 algorithm was generalized to this setting. Finally, many meaningful applications of non-commutative Gröbner bases were developed. Enumerating procedures were proposed to semi-decide some interesting undecidable problems. All the examples in the thesis were computed using the package gbmr of the computer algebra system ApCoCoA. The package was developed by the author. It contains dozens of functions for Gröbner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at http://www.apcocoa.org/.
In this thesis, we shall consider a certain class of algebraic cryptosystems called Gröbner Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryptosystem that is based on the theory of Gröbner basis in commutative polynomials rings. The security of this cryptosystem relies on the fact that the computation of Gröbner basis is, in general, EXPSPACE-hard. Cryptanalysis of these commutative Polly Cracker type cryptosystems is possible by using attacks that do not require the computation of Gröbner basis for breaking the system, for example, the attacks based on linear algebra. To secure these (commutative) Gröbner basis cryptosystems against various attacks, among others, Ackermann and Kreuzer introduced a general class of Gröbner Basis Cryptosystems that are based on the difficulty of computing module Gröbner bases over general non-commutative rings. The objective of this research is to describe a special class of such cryptosystems by introducing the Weyl Gröbner Basis Cryptosystems. We divide this class of cryptosystems in two parts namely the (left) Weyl Gröbner Basis Cryptosystems and Two-Sided Weyl Gröbner Basis Cryptosystems. We suggest to use Gröbner bases for left and two-sided ideals in Weyl algebras to construct specific instances of such cryptosystems. We analyse the resistance of these cryptosystems to the standard attacks and provide computational evidence that secure Weyl Gröbner Basis Cryptosystems can be built using left (resp. two-sided) Gröbner bases in Weyl algebras.