TY - THES A1 - Walsh, Florian T1 - Computing the Binomial Part of Polynomial Ideals N2 - Given an ideal in a polynomial ring over a field, we present a complete algorithm to compute its binomial part. Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-15096 ER - TY - THES A1 - Graf, Simone T1 - Kamerakalibrierung mit radialer Verzeichnung – die radiale essentielle Matrix T1 - Camera Calibration with Radial Distortion - the Radial Essential Matrix N2 - In der Bildverarbeitung wird die beobachtende Kamera meist als Lochkamera modelliert: ein Modell, das zahlreiche theoretische Vorteile bietet. So kann etwa das Abbildungsverhalten als projektive Abbildung aufgefasst werden. In einem Stereokamerasystem dieses Modells stehen korrespondierende Punkte – das sind Bildpunkte desselben 3D-Punktes – in einem linearen Zusammenhang, der auch ohne Kenntnis der Kameraparameter aus beobachteten Korrespondenzen geschätzt werden kann. Für die meisten Kameras, insbesondere für solche mit Weitwinkelobjektiven, ist die Modellannahme einer Lochkamera allerdings sichtbar unzureichend. Deshalb müssen zusätzlich zur Lochkamera noch Verzeichnungsabbildungen ins Modell integriert werden. In dieser Arbeit wird gezeigt, dass bei polynomialer radialer Verzeichnung die Parameter der Projektionsabbildung die Verzeichnungsparameter bestimmen. Dieses theoretische Ergebnis fließt in Algorithmen zur Kamerakalibrierung, d.h. zur Bestimmung der Parameter eines Kameramodells, ein. Diese wurden experimentell getestet und mit bestehenden Verfahren verglichen. Weiterhin wird die radiale essentielle Matrix eingeführt, die die Beziehung von korrespondierenden Punkten im Stereokamerafall bei radialer Verzeichnung beschreibt. Es werden vier Algorithmen vorgestellt, die diese theoretische Beziehung verwerten. Sie geben an, wie aus korrespondierenden Punkten die radiale essentielle Matrix geschätzt werden kann und welche Kameraparameter daraus gewonnen werden können. Damit ist beispielsweise eine Nachkalibrierung möglich. Auch diese Verfahren wurden implementiert und evaluiert. Umgekehrt ist bei bekannter radialer essentieller Matrix eine Einschränkung des Suchraums für korrespondierende Punkte möglich, die für die Rekonstruktion benötigt werden. KW - Optische Messtechnik KW - Kalibrieren KW - Stereokamera KW - Kamera KW - Korrespondenzproblem KW - Bildverarbeitung KW - Bildkorrelatio KW - Kamerakalibrierung KW - radiale Verzeichnung KW - epipolare Einschränkung KW - camera calibration KW - radial distortion KW - epipolar constraint Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12711 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization for uniform distributions on Cantor-like sets N2 - In this paper, the problem of optimal quantization is solved for uniform distributions on some higher dimensional, not necessarily self-similar $N-$adic Cantor-like sets. The optimal codebooks are determined and the optimal quantization error is calculated. The existence of the quantization dimension is characterized and it is shown that the quantization coefficient does not exist. The special case of self-similarity is also discussed. The conditions imposed are a separation property of the distribution and strict monotonicity of the first $N$ quantization error differences. Criteria for these conditions are proved and as special examples modified versions of classical fractal distributions are discussed. KW - Maßtheorie KW - Quantisierung KW - Iteriertes Funktionensystem KW - Fraktale Dimension KW - optimal quantization KW - quantization dimension KW - quantization coefficient KW - self-similar probabilities Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12449 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal vector quantization in terms of Wasserstein distance N2 - The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the R\'enyi-$\alpha$-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained $(\alpha = 1)$ and memory-size constrained $(\alpha = 0)$ quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by Gy\"{o}rgy and Linder. KW - Maßtheorie KW - Transporttheorie KW - Quantisierung KW - Entropie KW - Wasserstein distance KW - optimal quantization error KW - codecell convexity KW - R\'enyi-$\alpha$-entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-22502 N1 - This is a preprint of an article accepted for publication in the Journal of Multivariate Analysis ISSN 0047-259X. The original publication is available at http://www.elsevier.com/. The digital object identifier (DOI) of the definitive article is 10.1016/j.jmva.2011.04.005. ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal Quantization for Dyadic Homogeneous Cantor Distributions N2 - For a large class of dyadic homogeneous Cantor distributions in \mathbb{R}, which are not necessarily self-similar, we determine the optimal quantizers, give a characterization for the existence of the quantization dimension, and show the non-existence of the quantization coefficient. The class contains all self-similar dyadic Cantor distributions, with contraction factor less than or equal to \frac{1}{3}. For these distributions we calculate the quantization errors explicitly. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Quantization KW - homogeneous Cantor measures KW - Quantization dimension KW - Quantization coefficient Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-3845 N1 - Die Endfassung des Artikels kann beim Verfasser angefordert werden. Kontaktinformation: opus@uni-passau.de ER - TY - THES A1 - Ali, Rashid T1 - Weyl Gröbner Basis Cryptosystems N2 - 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. KW - Gröbner-Basis KW - Weyl-Algebra KW - Kryptologie KW - Public Key Cryptosystem KW - Non commutative Gröbner Basis Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23195 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - High-Resolution Scalar Quantization with Rényi Entropy Constraint N2 - We consider optimal scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha$. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for $\alpha=0$ (fixed-rate quantization) and $\alpha=1$ (entropy-constrained quantization). These results have recently been extended to quantization with R\'enyi entropy constraint of order $\alpha \ge r+1$. Here we consider the more challenging case $\alpha\in [-\infty,0)\cup (0,1)$ and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive. KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Companding KW - high-resolution asymptotics KW - optimal quantization KW - Rényi entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23787 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Hausdorff measure of uniform self-similar fractals N2 - Let d ≥ 1 be an integer and E a self-similar fractal set, which is the attractor of a uniform contracting iterated function system (UIFS) on Rd. Denote by D the Hausdorff dimension, by HD(E) the Hausdorff measure and by diam (E) the diameter of E. If the UIFS is parametrised by its contracting factor c, while the set ω of fixed points of the UIFS does not depend on c, we will show the existence of a positive constant depending only on ω, such that the Hausdorff dimension is smaller than one and HD = (E) D if c is smaller than this constant. We apply our result to modified versions of various classical fractals. Moreover we present a parametrised UIFS where ω depends on c and HD < diam(E)D, if c is small enough. KW - Maßtheorie KW - Iteriertes Funktionensystem KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Self-similar set KW - Hausdorff measure Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-17948 N1 - This is a preprint of an article accepted for publication in Analysis in Theory and Applications ISSN: 1672-4070 (print version) ISSN: 1573-8175 (electronic version) Copyright (c) by Springer. The original publication is available at www.springerlink.com ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization for the one-dimensional uniform distribution with Rényi -α-entropy constraints N2 - We establish the optimal quantization problem for probabilities under constrained Rényi-α-entropy of the quantizers. We determine the optimal quantizers and the optimal quantization error of one-dimensional uniform distributions including the known special cases α = 0 (restricted codebook size) and α = 1 (restricted Shannon entropy). KW - Maßtheorie KW - Quantisierung KW - Entropie KW - optimal quantization KW - uniform distribution KW - Rényi-α-entropy Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16983 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Error bounds for high-resolution quantization with Rényi - α - entropy constraints N2 - We consider the problem of optimal quantization with norm exponent r > 0 for Borel probabilities on Rd under constrained Rényi-α-entropy of the quantizers. If the bound on the entropy becomes large, then sharp asymptotics for the optimal quantization error are well-known in the special cases α = 0 (memory-constrained quantization) and α = 1 (Shannon-entropy-constrained quantization). In this paper we determine sharp asymptotics for the optimal quantization error under large entropy bound with entropy parameter α ∈ [1+r/d, ∞]. For α ∈ [0,1+r/d[ we specify the asymptotical order of the optimal quantization error under large entropy bound. The optimal quantization error decays exponentially fast with the entropy bound and the exact decay rate is determined for all α ∈ [0, ∞]. KW - Maßtheorie KW - Quantisierung KW - Vektorquantisierung KW - Entropie KW - Vector quantization KW - high-resolution quantization KW - Rényi-α-entropy KW - approximation of probabilities Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16647 ER - TY - THES A1 - Kreitmeier, Wolfgang T1 - Optimale Quantisierung verallgemeinerter Cantor-Verteilungen N2 - Für verallgemeinerte Cantor-Verteilungen, die im Eindimensionalen mittels klassischer Wischkonstruktion bzw. in höheren Dimensionen über iterierte Funktionensysteme definiert werden, wird das Problem der optimalen Quantisierung unter bestimmten Voraussetzungen vollständig gelöst. Es werden die optimalen Codebücher bestimmt und Formeln für den optimalen Quantisierungsfehler bewiesen. Im eindimensionalen Fall wird eine Existenzcharakterisierung der Quantisierungsdimension gegeben und unter bestimmten Voraussetzungen die Nichtexistenz des Quantisierungskoeffizienten gezeigt. Auch in höheren Dimensionen wird für die betrachteten Verteilungen bewiesen, dass der Quantisierungskoeffizient, bei existenter Quantisierungsdimension, nicht existiert. Die gewonnenen Resultate werden auf die Gleichverteilungen von modifizierten klassischen fraktalen Mengen, wie das Sierpinski-Dreieck, die Cantormenge und den Cantor-Staub angewandt. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Sierpinski-Menge KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Optimale Quantisierung KW - homogene Cantormaße KW - Quantisierungsdimension KW - Quantisierungskoeffizient KW - Sierpinski-Dreieck KW - Optimal Quantization KW - homogeneous Cantor measures KW - Quantization dimension KW - Quantization coefficient KW - Sierpinski Gasket Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-913 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization of probabilities concentrated on small balls N2 - We consider probability distributions which are uniformly distributed on a disjoint union of balls with equal radius. For small enough radius the optimal quantization error is calculated explicitly in terms of the ball centroids. We apply the results to special self-similar measures. KW - Maßtheorie KW - Quantisierung KW - Iteriertes Funktionensystem KW - Schwerpunkt KW - optimal quantization KW - centroid KW - self-similar probabilities Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12010 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Asymptotic order of quantization for Cantor distributions in terms of Euler characteristic, Hausdorff and Packing measure N2 - For homogeneous one-dimensional Cantor sets, which are not necessarily self-similar, we show under some restrictions that the Euler exponent equals the quantization dimension of the uniform distribution on these Cantor sets. Moreover for a special sub-class of these sets we present a linkage between the Hausdorff and the Packing measure of these sets and the high-rate asymptotics of the quantization error. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Homogeneous Cantor set KW - Euler characteristic KW - Euler exponent KW - quantization dimension KW - quantization coefficient KW - Hausdorff dimension Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-7374 N1 - Die Endfassung des Artikels kann beim Verfasser angefordert werden. Kontaktinformation: opus@uni-passau.de ER - TY - THES A1 - Lauren, Verena T1 - Semilineare Approximation in der Bildrekonstruktion N2 - In der Bildverarbeitung spielen Segmentierungsalgorithmen, bei denen die Art der zu segmentierenden Menge schon im Voraus festgelegt werden kann und nur noch ihre Größe und Lage angepasst werden muss, eine eher untergeordnete Rolle. Gründe hierfür sind vor allem komplizierte Zielfunktionen und daraus resultierende lange Rechenzeiten, die zudem meist kein optimales Ergebnis liefern. Dabei kann eine mengenbasierte Segmentierung durchaus sinnvoll eingesetzt werden, wenn gewisse Rahmenbedingungen eingehalten werden. In dieser Arbeit wird eine Theorie zur allgemeinen mengenbasierten Segmentierung vorgestellt und untersucht, unter welchen Bedingungen optimale Segmentierungsergebnisse erreicht werden können. Die anschließenden Anwendungen bestätigen die Nützlichkeit dieser Theorie. KW - Optimale Rekonstruktion KW - Rekonstruktion KW - Bildverarbeitung KW - Objektrekonstruktion KW - Bildrekonstruktion KW - image reconstruction KW - image processing KW - object reconstruction Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-730 ER - TY - THES A1 - Fischer, Andreas T1 - Peano-differentiable functions in O-Minimal structures T1 - Peano-differenzierbare Funktionen in o-minimalen Strukturen N2 - We discuss several aspects of Peano-differentiable functions which are definable in an o-minimal structure expanding a real closed field. After recalling some already known results about o-minimal structures we develop techniques for the intrinsic study of differentiable functions in these structures. After this we study (ordinary) differentiable functions definable in an o-minimal structure and their continuiuty properties along curves of different differentiability classes. Then we generalise (ordinary) differentiability to Peano-differentiability. We study differentiability of certain Peano-derivatives of definable functions and characterise the sets of non-continuity of these derivatives. In the end we study extendability of these functions defined on closed sets and give sufficient conditions by which we can extend functions as Peano-differentiable functions. KW - Semialgebraische Menge KW - Reelle Analysis KW - Reell-abgeschlossener Körper KW - Differenzierbare Funktion KW - Reelle algebraische Geometrie KW - o-minimale Struktur KW - Peano-differenzierbare Funktion KW - o-minimal structure KW - Peano-differentiable function Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-673 ER - TY - THES A1 - Limbeck, Jan T1 - Computation of Approximate Border Bases and Applications T1 - Berechnung und Anwendungen Approximativer Randbasen N2 - This thesis addresses some of the algorithmic and numerical challenges associated with the computation of approximate border bases, a generalisation of border bases, in the context of the oil and gas industry. The concept of approximate border bases was introduced by D. Heldt, M. Kreuzer, S. Pokutta and H. Poulisse in "Approximate computation of zero-dimensional polynomial ideals" as an effective mean to derive physically relevant polynomial models from measured data. The main advantages of this approach compared to alternative techniques currently in use in the (hydrocarbon) industry are its power to derive polynomial models without additional a priori knowledge about the underlying physical system and its robustness with respect to noise in the measured input data. The so-called Approximate Vanishing Ideal (AVI) algorithm which can be used to compute approximate border bases and which was also introduced by D. Heldt et al. in the paper mentioned above served as a starting point for the research which is conducted in this thesis. A central aim of this work is to broaden the applicability of the AVI algorithm to additional areas in the oil and gas industry, like seismic imaging and the compact representation of unconventional geological structures. For this purpose several new algorithms are developed, among others the so-called Approximate Buchberger Möller (ABM) algorithm and the Extended-ABM algorithm. The numerical aspects and the runtime of the methods are analysed in detail - based on a solid foundation of the underlying mathematical and algorithmic concepts that are also provided in this thesis. It is shown that the worst case runtime of the ABM algorithm is cubic in the number of input points, which is a significant improvement over the biquadratic worst case runtime of the AVI algorithm. Furthermore, we show that the ABM algorithm allows us to exercise more direct control over the essential properties of the computed approximate border basis than the AVI algorithm. The improved runtime and the additional control turn out to be the key enablers for the new industrial applications that are proposed here. As a conclusion to the work on the computation of approximate border bases, a detailed comparison between the approach in this thesis and some other state of the art algorithms is given. Furthermore, this work also addresses one important shortcoming of approximate border bases, namely that central concepts from exact algebra such as syzygies could so far not be translated to the setting of approximate border bases. One way to mitigate this problem is to construct a "close by" exact border bases for a given approximate one. Here we present and discuss two new algorithmic approaches that allow us to compute such close by exact border bases. In the first one, we establish a link between this task, referred to as the rational recovery problem, and the problem of simultaneously quasi-diagonalising a set of complex matrices. As simultaneous quasi-diagonalisation is not a standard topic in numerical linear algebra there are hardly any off-the-shelf algorithms and implementations available that are both fast and numerically adequate for our purposes. To bridge this gap we introduce and study a new algorithm that is based on a variant of the classical Jacobi eigenvalue algorithm, which also works for non-symmetric matrices. As a second solution of the rational recovery problem, we motivate and discuss how to compute a close by exact border basis via the minimisation of a sum of squares expression, that is formed from the polynomials in the given approximate border basis. Finally, several applications of the newly developed algorithms are presented. Those include production modelling of oil and gas fields, reconstruction of the subsurface velocities for simple subsurface geometries, the compact representation of unconventional oil and gas bodies via algebraic surfaces and the stable numerical approximation of the roots of zero-dimensional polynomial ideals. KW - Computeralgebra KW - Numerische Mathematik KW - Erdöl KW - Diagonalisierung KW - Modellierung KW - Simultane Quasi-Diagonalisierung KW - Approximative Randbasen KW - Öl und Gas Industrie KW - Data Driven Modelling KW - Buchberger-Möller Algorithmus KW - simultaneous quasi-diagonalization KW - approximate border bases KW - oil and gas industry KW - data driven modelling KW - Buchberger-Moeller algorithm Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27197 ER - TY - THES A1 - Capco, Jose T1 - Real Closed * Rings T1 - Reelle abgeschlossene * Ringe N2 - In this dissertation I examine a definition of real closure of commutative unitary reduced rings. I also give a characterization of rings that are real closed in this context and how one is able to arrive to such a real closure. There are sufficient examples to help the reader get a feel for real closed * rings and the real closure * of commutative unitary rings. KW - real closed rings KW - real closure Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-25915 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - Entropy Density and Mismatch in High-Rate Scalar Quantization with Rényi Entropy Constraint N2 - Properties of scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha\in (0,1)$ are investigated. For an asymptotically (high-rate) optimal sequence of quantizers, the contribution to the R\'enyi entropy due to source values in a fixed interval is identified in terms of the "entropy density" of the quantizer sequence. This extends results related to the well-known point density concept in optimal fixed-rate quantization. A dual of the entropy density result quantifies the distortion contribution of a given interval to the overall distortion. The distortion loss resulting from a mismatch of source densities in the design of an asymptotically optimal sequence of quantizers is also determined. This extends Bucklew's fixed-rate ($\alpha=0$) and Gray \emph{et al.}'s variable-rate ($\alpha=1$)mismatch results to general values of the entropy order parameter $\alpha$ KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Asymptotic quantization theory KW - distortion density KW - entropy density KW - quantizer mismatch KW - Rényi-entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26132 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 ER - TY - THES A1 - Ullah, Ehsan T1 - New Techniques for Polynomial System Solving N2 - Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gröbner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm. We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques. KW - Polynomlösung KW - Algebra KW - Lineare Algebra KW - Algorithmus KW - polynomial system solving KW - techniques KW - linear algebra KW - border bases KW - mutant strategies Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26815 ER - TY - THES A1 - Xiu, Xingqiang T1 - Non-commutative Gröbner Bases and Applications N2 - 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/. KW - Gröbner-Basis KW - Assoziativer Ring KW - Endlich erzeugter Modul KW - Gruppentheorie KW - non-commutative polynomial KW - non-commutative Gröbner basis KW - applications KW - Gebauer-Möller KW - optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26827 ER -