Kaiserslautern - Fachbereich Mathematik
Refine
Document Type
- Doctoral Thesis (3) (remove)
Has Fulltext
- yes (3)
Keywords
- Gröbner-Basis (3) (remove)
Faculty / Organisational entity
Zusammenfassung. In dieser Arbeit werden Probleme der numerischen Lösung finiter Differenzenverfahren partieller Differentialgleichungen in einem algebraischen Ansatz behandelt. Es werden sowohl theoretische Ergebnisse präsentiert als auch die praktische Implementierung mithilfe der Systeme SINGULAR und QEPCAD vorgeführt. Dabei beziehen sich die algebraischen Methoden auf zwei unterschiedliche Aspekte bei finiten Differenzenverfahren: die Erzeugung von Schemata mithilfe von Gröbnerbasen und die darauf folgende Stabilitätsanalyse mittels Quantorenelimination durch algebraische zylindrische Dekomposition. Beim Aufbau der Arbeit werden in den ersten drei Kapiteln in einer Rückschau die nötigen Begriffe aus der Computeralgebra gelegt, die Grundzüge der numerischen Konvergenztheorie finiter Differenzenschemata erklärt sowie die Anwendung des CAD-Algorithmus zur Quantorenelimierung skizziert. Das Kapitel 4 entwickelt ausgehend vom zugrunde liegenden Kontext die Formulierung und die dafür nötigen Bedingungen an Differenzenschemata, die algebraisch nach Definition ein Ideal in einem Polynomring darstellen. Neben der praktischen Handhabbarkeit der Objekte liegt die Betonung auf größtmöglicher Allgemeinheit in den Definitionen der Begriffe. Es werden äquivalente Wege der Erzeugung sowie Eigenschaften der Eindeutigkeit unter sehr speziellen Bedingungen an die verwendeten Approximationen gezeigt. Die Anwendung des CAD-Algorithmus auf die Abschätzung des Symbols eines Schemas wird erläutert. Das fünfte Kapitel beschreibt die SINGULAR-Bibliothek findiff.lib, welche das Zusammenspiel von SINGULAR und QEPCAD garantiert und eine vollständige Automatisierung der Erzeugung und Stabilitätsanalyse eines finiten Differenzenverfahrens ermöglicht.
This thesis is devoted to applying symbolic methods to the problems of decoding linear codes and of algebraic cryptanalysis. The paradigm we employ here is as follows. We reformulate the initial problem in terms of systems of polynomial equations over a finite field. The solution(s) of such systems should yield a way to solve the initial problem. Our main tools for handling polynomials and polynomial systems in such a paradigm is the technique of Gröbner bases and normal form reductions. The first part of the thesis is devoted to formulating and solving specific polynomial systems that reduce the problem of decoding linear codes to the problem of polynomial system solving. We analyze the existing methods (mainly for the cyclic codes) and propose an original method for arbitrary linear codes that in some sense generalizes the Newton identities method widely known for cyclic codes. We investigate the structure of the underlying ideals and show how one can solve the decoding problem - both the so-called bounded decoding and more general nearest codeword decoding - by finding reduced Gröbner bases of these ideals. The main feature of the method is that unlike usual methods based on Gröbner bases for "finite field" situations, we do not add the so-called field equations. This tremendously simplifies the underlying ideals, thus making feasible working with quite large parameters of codes. Further we address complexity issues, by giving some insight to the Macaulay matrix of the underlying systems. By making a series of assumptions we are able to provide an upper bound for the complexity coefficient of our method. We address also finding the minimum distance and the weight distribution. We provide solid experimental material and comparisons with some of the existing methods in this area. In the second part we deal with the algebraic cryptanalysis of block iterative ciphers. Namely, we analyze the small-scale variants of the Advanced Encryption Standard (AES), which is a widely used modern block cipher. Here a cryptanalyst composes the polynomial systems which solutions should yield a secret key used by communicating parties in a symmetric cryptosystem. We analyze the systems formulated by researchers for the algebraic cryptanalysis, and identify the problem that conventional systems have many auxiliary variables that are not actually needed for the key recovery. Moreover, having many such auxiliary variables, specific to a given plaintext/ciphertext pair, complicates the use of several pairs which is common in cryptanalysis. We thus provide a new system where the auxiliary variables are eliminated via normal form reductions. The resulting system in key-variables only is then solved. We present experimental evidence that such an approach is quite good for small scaled ciphers. We investigate further our approach and employ the so-called meet-in-the-middle principle to see how far one can go in analyzing just 2-3 rounds of scaled ciphers. Additional "tuning techniques" are discussed together with experimental material. Overall, we believe that the material of this part of the thesis makes a step further in algebraic cryptanalysis of block ciphers.
Non-commutative polynomial algebras appear in a wide range of applications, from quantum groups and theoretical physics to linear differential and difference equations. In the thesis, we have developed a framework, unifying many important algebras in the classes of \(G\)- and \(GR\)-algebras and studied their ring-theoretic properties. Let \(A\) be a \(G\)-algebra in \(n\) variables. We establish necessary and sufficient conditions for \(A\) to have a Poincar'e-Birkhoff-Witt (PBW) basis. Further on, we show that besides the existence of a PBW basis, \(A\) shares some other properties with the commutative polynomial ring \(\mathbb{K}[x_1,\ldots,x_n]\). In particular, \(A\) is a Noetherian integral domain of Gel'fand-Kirillov dimension \(n\). Both Krull and global homological dimension of \(A\) are bounded by \(n\); we provide examples of \(G\)-algebras where these inequalities are strict. Finally, we prove that \(A\) is Auslander-regular and a Cohen-Macaulay algebra. In order to perform symbolic computations with modules over \(GR\)-algebras, we generalize Gröbner bases theory, develop and respectively enhance new and existing algorithms. We unite the most fundamental algorithms in a suite of applications, called "Gröbner basics" in the literature. Furthermore, we discuss algorithms appearing in the non-commutative case only, among others two-sided Gröbner bases for bimodules, annihilators of left modules and operations with opposite algebras. An important role in Representation Theory is played by various subalgebras, like the center and the Gel'fand-Zetlin subalgebra. We discuss their properties and their relations to Gröbner bases, and briefly comment some aspects of their computation. We proceed with these subalgebras in the chapter devoted to the algorithmic study of morphisms between \(GR\)-algebras. We provide new results and algorithms for computing the preimage of a left ideal under a morphism of \(GR\)-algebras and show both merits and limitations of several methods that we propose. We use this technique for the computation of the kernel of a morphism, decomposition of a module into central characters and algebraic dependence of pairwise commuting elements. We give an algorithm for computing the set of one-dimensional representations of a \(G\)-algebra \(A\), and prove, moreover, that if the set of finite dimensional representations of \(A\) over a ground field \(K\) is not empty, then the homological dimension of \(A\) equals \(n\). All the algorithms are implemented in a kernel extension Plural of the computer algebra system Singular. We discuss the efficiency of computations and provide a comparison with other computer algebra systems. We propose a collection of benchmarks for testing the performance of algorithms; the comparison of timings shows that our implementation outperforms all of the modern systems with the combination of both broad functionality and fast implementation. In the thesis, there are many new non-trivial examples, and also the solutions to various problems, arising in different fields of mathematics. All of them were obtained with the developed theory and the implementation in Plural, most of them are treated computationally in this thesis for the first time.