TY - THES A1 - Seidl, Andreas T1 - Cylindrical Decomposition Under Application-Oriented Paradigms T1 - Zylindrische Dekomposition unter anwendungsorientierten Paradigmen N2 - Quantifier elimination (QE) is a powerful tool for problem solving. Once a problem is expressed as a formula, such a method converts it to a simpler, quantifier-free equivalent, thus solving the problem. Particularly many problems live in the domain of real numbers, which makes real QE very interesting. Among the so far implemented methods, QE by cylindrical algebraic decomposition (CAD) is the most important complete method. The aim of this thesis is to develop CAD-based algorithms, which can solve more problems in practice and/or provide more interesting information as output. An algorithm that satisfies these standards would concentrate on generic cases and postpone special and degenerated ones to be treated separately or to be abandoned completely. It would give a solution, which is locally correct for a region the user is interested in. It would give answers, which can provide much valuable information in particular for decision problems. It would combine these methods with more specialized ones, for subcases that allow for. It would exploit degrees of freedom in the algorithms by deciding to proceed in a way that promises to be efficient. It is the focus of this dissertation to treat these challenges. Algorithms described here are implemented in the computer logic system REDLOG and ship with the computer algebra system REDUCE. KW - Quantorenelimination KW - cylindrical algebraic decomposition KW - CAD KW - cylindrical subdecomposition KW - SCAD KW - quantifier elimination KW - QE Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-816 ER - 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 - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Asymptotic optimality of scalar Gersho quantizers N2 - In his famous paper Gersho stressed that the codecells of optimal quantizers asymptotically make an equal contribution to the distortion of the quantizer. Motivated by this fact, we investigate in this paper quantizers in the scalar case, where each codecell contributes with exactly the same portion to the quantization error. We show that such quantizers of Gersho type - or Gersho quantizers for short - exist for non-atomic scalar distributions. As a main result we prove that Gersho quantizers are asymptotically optimal. KW - Maßtheorie KW - Informationstheorie KW - Signaltheorie KW - Approximation KW - Kodierung KW - Quantisierung KW - Asymptotically optimal quantization KW - Quantization error KW - Scalar quantization KW - Gersho quantizer KW - High rate quantization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-27080 N1 - This is a preprint of an article accepted for publication in Constructive Approximation, ISSN: 0176-4276 (print version) ISSN: 1432-0940 (electronic version) Copyright (c) by Springer. The final publication is available at link.springer.com URL: http://dx.doi.org/10.1007/s00365-013-9214-2 ER - TY - THES A1 - Sonnleitner, Mathias T1 - The power of random information for numerical approximation and integration N2 - This thesis investigates the quality of randomly collected data by employing a framework built on information-based complexity, a field related to the numerical analysis of abstract problems. The quality or power of gathered information is measured by its radius which is the uniform error obtainable by the best possible algorithm using it. The main aim is to present progress towards understanding the power of random information for approximation and integration problems. In the first problem considered, information given by linear functionals is used to recover vectors, in particular from generalized ellipsoids. This is related to the approximation of diagonal operators which are important objects of study in the theory of function spaces. We obtain upper bounds on the radius of random information both in a convex and a quasi-normed setting, which extend and, in some cases, improve existing results. We conjecture and partially establish that the power of random information is subject to a dichotomy determined by the decay of the length of the semiaxes of the generalized ellipsoid. Second, we study multivariate approximation and integration using information given by function values at sampling point sets. We obtain an asymptotic characterization of the radius of information in terms of a geometric measure of equidistribution, the distortion, which is well known in the theory of quantization of measures. This holds for isotropic Sobolev as well as Hölder and Triebel-Lizorkin spaces on bounded convex domains. We obtain that for these spaces, depending on the parameters involved, typical point sets are either asymptotically optimal or worse by a logarithmic factor, again extending and improving existing results. Further, we study isotropic discrepancy which is related to numerical integration using linear algorithms with equal weights. In particular, we analyze the quality of lattice point sets with respect to this criterion and obtain that they are suboptimal compared to uniform random points. This is in contrast to the approximation of Sobolev functions and resolves an open question raised in the context of a possible low discrepancy construction on the two-dimensional sphere. KW - information-based complexity KW - cubature KW - numerical approximation KW - discrepancy KW - Monte Carlo integration KW - Komplexität / Algorithmus KW - Numerische Integration KW - Monte-Carlo-Integration KW - Gewichteter Funktionenraum KW - Scattered-Data-Interpolation Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-11305 ER - TY - THES A1 - Bachl, Walter T1 - Interaktives orthogonales Zeichnen von planaren Graphen N2 - Die Arbeit beschäftigt sich mit dem automatischen Zeichnen von Graphen. Hier wird ein interaktiver Ansatz untersucht, bei dem der Graph mit einer Menge von Operationen Schritt für Schritt aufgebaut wird. Der Zielgraph und die Einfügereihenfolge sind dabei nicht fest vorgegeben, sondern werden vom Benutzer bestimmt. In der Arbeit wird vor allem ein Szenario für zweifach zusammenhängende Graphen untersucht und ein für diese Zwecke passendes Zeichenmodell entwickelt. Dieser Ansatz wird dann um verschiedene Varianten erweitert. Außerdem wird gezeigt, dass das flächenminimale Zeichnen in dem neu entwickelten Zeichenmodell NP-vollständig ist. KW - Graphenzeichnen KW - Graphalgorithmen KW - Flächenminimales Zeichnen Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-392 ER - TY - THES A1 - Jovanovic, Philipp T1 - Analysis and Design of Symmetric Cryptographic Algorithms N2 - This doctoral thesis is dedicated to the analysis and the design of symmetric cryptographic algorithms. In the first part of the dissertation, we deal with fault-based attacks on cryptographic circuits which belong to the field of active implementation attacks and aim to retrieve secret keys stored on such chips. Our main focus lies on the cryptanalytic aspects of those attacks. In particular, we target block ciphers with a lightweight and (often) non-bijective key schedule where the derived subkeys are (almost) independent from each other. An attacker who is able to reconstruct one of the subkeys is thus not necessarily able to directly retrieve other subkeys or even the secret master key by simply reversing the key schedule. We introduce a framework based on differential fault analysis that allows to attack block ciphers with an arbitrary number of independent subkeys and which rely on a substitution-permutation network. These methods are then applied to the lightweight block ciphers LED and PRINCE and we show in both cases how to recover the secret master key requiring only a small number of fault injections. Moreover, we investigate approaches that utilize algebraic instead of differential techniques for the fault analysis and discuss advantages and drawbacks. At the end of the first part of the dissertation, we explore fault-based attacks on the block cipher Bel-T which also has a lightweight key schedule but is not based on a substitution-permutation network but instead on the so-called Lai-Massey scheme. The framework mentioned above is thus not usable against Bel-T. Nevertheless, we also present techniques for the case of Bel-T that enable full recovery of the secret key in a very efficient way using differential fault analysis. In the second part of the thesis, we focus on authenticated encryption schemes. While regular ciphers only protect privacy of processed data, authenticated encryption schemes also secure its authenticity and integrity. Many of these ciphers are additionally able to protect authenticity and integrity of so-called associated data. This type of data is transmitted unencrypted but nevertheless must be protected from being tampered with during transmission. Authenticated encryption is nowadays the standard technique to protect in-transit data. However, most of the currently deployed schemes have deficits and there are many leverage points for improvements. With NORX we introduce a novel authenticated encryption scheme supporting associated data. This algorithm was designed with high security, efficiency in both hardware and software, simplicity, and robustness against side-channel attacks in mind. Next to its specification, we present special features, security goals, implementation details, extensive performance measurements and discuss advantages over currently deployed standards. Finally, we describe our preliminary security analysis where we investigate differential and rotational properties of NORX. Noteworthy are in particular the newly developed techniques for differential cryptanalysis of NORX which exploit the power of SAT- and SMT-solvers and have the potential to be easily adaptable to other encryption schemes as well. N2 - Diese Doktorarbeit beschäftigt sich mit der Analyse und dem Entwurf von symmetrischen kryptographischen Algorithmen. Im ersten Teil der Dissertation befassen wir uns mit fehlerbasierten Angriffen auf kryptographische Schaltungen, welche dem Gebiet der aktiven Seitenkanalangriffe zugeordnet werden und auf die Rekonstruktion geheimer Schlüssel abzielen, die auf diesen Chips gespeichert sind. Unser Hauptaugenmerk liegt dabei auf den kryptoanalytischen Aspekten dieser Angriffe. Insbesondere beschäftigen wir uns dabei mit Blockchiffren, die leichtgewichtige und eine (oft) nicht-bijektive Schlüsselexpansion besitzen, bei denen die erzeugten Teilschlüssel voneinander (nahezu) unabhängig sind. Ein Angreifer, dem es gelingt einen Teilschlüssel zu rekonstruieren, ist dadurch nicht in der Lage direkt weitere Teilschlüssel oder sogar den Hauptschlüssel abzuleiten indem er einfach die Schlüsselexpansion umkehrt. Wir stellen Techniken basierend auf differenzieller Fehleranalyse vor, die es ermöglichen Blockchiffren zu analysieren, welche eine beliebige Anzahl unabhängiger Teilschlüssel einsetzen und auf Substitutions-Permutations Netzwerken basieren. Diese Methoden werden im Anschluss auf die leichtgewichtigen Blockchiffren LED und PRINCE angewandt und wir zeigen in beiden Fällen wie der komplette geheime Schlüssel mit einigen wenigen Fehlerinjektionen rekonstruiert werden kann. Darüber hinaus untersuchen wir Methoden, die algebraische statt differenzielle Techniken der Fehleranalyse einsetzen und diskutieren deren Vor- und Nachteile. Am Ende des ersten Teils der Dissertation befassen wir uns mit fehlerbasierten Angriffen auf die Blockchiffre Bel-T, welche ebenfalls eine leichtgewichtige Schlüsselexpansion besitzt jedoch nicht auf einem Substitutions-Permutations Netzwerk sondern auf dem sogenannten Lai-Massey Schema basiert. Die oben genannten Techniken können daher bei Bel-T nicht angewandt werden. Nichtsdestotrotz werden wir auch für den Fall von Bel-T Verfahren vorstellen, die in der Lage sind den vollständigen geheimen Schlüssel sehr effizient mit Hilfe von differenzieller Fehleranalyse zu rekonstruieren. Im zweiten Teil der Doktorarbeit beschäftigen wir uns mit authentifizierenden Verschlüsselungsverfahren. Während gewöhnliche Chiffren nur die Vertraulichkeit der verarbeiteten Daten sicherstellen, gewährleisten authentifizierende Verschlüsselungsverfahren auch deren Authentizität und Integrität. Viele dieser Chiffren sind darüber hinaus in der Lage auch die Authentizität und Integrität von sogenannten assoziierten Daten zu gewährleisten. Daten dieses Typs werden in nicht-verschlüsselter Form übertragen, müssen aber dennoch gegen unbefugte Veränderungen auf dem Transportweg geschützt sein. Authentifizierende Verschlüsselungsverfahren bilden heutzutage die Standardtechnologie um Daten während der Übertragung zu beschützen. Aktuell eingesetzte Verfahren weisen jedoch oftmals Defizite auf und es existieren vielfältige Ansatzpunkte für Verbesserungen. Mit NORX stellen wir ein neuartiges authentifizierendes Verschlüsselungsverfahren vor, welches assoziierte Daten unterstützt. Dieser Algorithmus wurde vor allem im Hinblick auf Einsatzgebiete mit hohen Sicherheitsanforderungen, Effizienz in Hardware und Software, Einfachheit, und Robustheit gegenüber Seitenkanalangriffen entwickelt. Neben der Spezifikation präsentieren wir besondere Eigenschaften, angestrebte Sicherheitsziele, Details zur Implementierung, umfassende Performanz-Messungen und diskutieren Vorteile gegenüber aktuellen Standards. Schließlich stellen wir Ergebnisse unserer vorläufigen Sicherheitsanalyse vor, bei der wir uns vor allem auf differenzielle Merkmale und Rotationseigenschaften von NORX konzentrieren. Erwähnenswert sind dabei vor allem die für die differenzielle Kryptoanalyse von NORX entwickelten Techniken, die auf die Effizienz von SAT- und SMT-Solvern zurückgreifen und das Potential besitzen relativ einfach auch auf andere Verschlüsselungsverfahren übertragen werden zu können. KW - cryptography KW - cryptanalysis KW - authenticated encryption KW - NORX KW - fault-based attacks KW - Kryptologie KW - Computersicherheit Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-3319 ER - TY - THES A1 - Le, Ngoc Long T1 - Various Differents for 0-Dimensional Schemes and Applications N2 - This thesis attempts to investigate the Noether, Dedekind, and Kähler differents for a 0-dimensional scheme X in the projective n-space P^n_K over an arbitrary field K. In particular, we focus on studying the relations between the algebraic structure of these differents and geometric properties of the scheme X. In Chapter 1 we give an outline to the problems this thesis is concerned with, a brief literature review for each problem, and the main results regarding these problems. Chapter 2 contains background results that we will need in the subsequent chapters. We introduce the concept of maximal p_j-subschemes of a 0-dimensional scheme X and give some descriptions of them and their Hilbert functions. Furthermore, we generalize the notion of a separator of a subscheme of X of degree deg(X)-1 to a set of separators of a maximal p_j-subscheme of X. In Chapter 3 we explore the Noether, Dedekind, and Kähler differents for 0-dimensional schemes X. First we define these differents for X, and take a look at how to compute these differents and examine their relations. Then we give an answer to the question "What are the Hilbert functions of these differents?" in some cases. In Chapter 4 we use the differents to investigate the Cayley-Bacharach property of 0-dimensional schemes over an arbitrary field K. The principal results of this chapter are characterizations of CB-schemes and of arithmetically Gorenstein schemes in terms of their Dedekind differents and a criterion for a 0-dimensional smooth scheme to be a complete intersection. We also generalize some results such as Dedekind's formula and the characterization of the Cayley-Bacharach property by using Liaison theory. In addition, several propositions on the uniformities are proven. In Chapter 5 we are interested in studying the Noether, Dedekind, and Kähler differents for finite special classes of schemes and finding out some applications of these differents. First, we investigate these differents for reduced 0-dimensional almost complete intersections X in P^n_K over a perfect field K. Then we investigate the relationships between these differents and the i-th Fitting ideals of the module of Kähler differentials of the homogeneous coordinate ring of X. Finally, we look more closely at the Hilbert functions and the regularity indices of these differents for fat point schemes. KW - Kommutativer Ring KW - Dimension 0 KW - Differente Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-3386 ER - TY - THES A1 - Lehner, Sabrina T1 - The Asymptotic Behaviour of the Riemann Mapping Function at Analytic Cusps N2 - The well-known Riemann Mapping Theorem states the existence of a conformal map of a simply connected proper domain of the complex plane onto the upper half plane. One of the main topics in geometric function theory is to investigate the behaviour of the mapping functions at the boundary of such domains. In this work, we always assume that a piecewise analytic boundary is given. Hereby, we have to distinguish regular and singular boundary points. While the asymptotic behaviour for regular boundary points can be investigated by using the Schwarz Reflection at analytic arcs, the situation for singular boundary points is far more complicated. In the latter scenario two cases have to be differentiated: analytic corners and analytic cusps. The first part of the thesis deals with the asymptotic behaviour at analytic corners where the opening angle is greater than 0. The results of Lichtenstein and Warschawski on the asymptotic behaviour of the Riemann map and its derivatives at an analytic corner are presented as well as the much stronger result of Lehman that the mapping function can be developed in a certain generalised power series which in turn enables to examine the o-minimal content of the Riemann Mapping Theorem. To obtain a similar statement for domains with analytic cusps, it is necessary to investigate the asymptotic behaviour of a Riemann map at the cusp and based on this result to determine the asymptotic power series expansion. Therefore, the aim of the second part of this work is to investigate the asymptotic behaviour of a Riemann map at an analytic cusp. A simply connected domain has an analytic cusp if the boundary is locally given by two analytic arcs such that the interior angle vanishes. Besides the asymptotic behaviour of the mapping function, the behaviour of its derivatives, its inverse, and the derivatives of the inverse are analysed. Finally, we present a conjecture on the asymptotic power series expansion of the mapping function at an analytic cusp. N2 - Der wohlbekannte Riemannsche Abbildungssatz liefert die Existenz einer konformen Abbildung eines einfach zusammenhängenden, echten Teilgebietes der komplexen Ebene auf die obere Halbebene. Die Untersuchung des Verhaltens solcher Abbildungen am Rand der Gebiete ist ein zentrales Thema der geometrischen Funktionentheorie. In der vorliegenden Arbeit gehen wir stets von einem stückweise analytischen Rand aus. Dabei müssen wir reguläre und singuläre Randpunkte unterscheiden. Während das Verhalten einer Riemann-Abbildung an regulären Randpunkten mit Hilfe des Schwarzschen Spiegelungsprinzips an analytischen Kurvenbögen einfach zu bestimmen ist, gestaltet sich dies in der Situation von singulären Randpunkten sehr viel komplizierter. In diesem Fall müssen wir erneut eine Unterscheidung treffen, nämlich ob es sich um eine analytische Ecke oder eine analytische Spitze handelt. Der erste Teil der Dissertation beschäftigt sich mit dem asymptotischen Verhalten einer Riemann-Abbildung an analytischen Ecken. Eine solche liegt vor, falls der Öffnungswinkel zwischen den analytischen Kurvenstücken an dem singulären Randpunkt größer als 0 ist. Es werden die Ergebnisse von Lichtenstein und Warschawski präsentiert, die sich mit dem Verhalten der Riemann-Abbildung und deren Ableitungen beschäftigt haben, sowie das stärkere Ergebnis von Lehman welches besagt, dass die Abbildung in eine verallgemeinerte Potenzreihe entwickelt werden kann. Unter Verwendung dieses Resultats konnte bereits der o-minimale Gehalt des Riemannschen Abbildungssatzes untersucht werden. Um ein ähnliches Ergebnis für den Fall, dass das Gebiet analytische Spitzen hat, zu erhalten, benötigen wir zunächst das asymptotische Verhalten der Riemann-Abbildung an einer Spitze. Darauf aufbauend kann die asymptotische Reihenentwicklung untersucht werden. Daher zielt der zweite Abschnitt dieser Arbeit darauf ab, das Verhalten der Abbildung an einer Spitze zu bestimmen. Dabei sprechen wir von einer analytischen Spitze, wenn der Rand des Gebietes lokal durch zwei reguläre analytische Bögen gegeben ist, deren Öffnungswinkel verschwindet. Neben dem asymptotischen Verhalten der Abbildung wird auch das Verhalten der Ableitungen, ihrer Umkehrfunktion und deren Ableitungen untersucht. Abschließend präsentieren wir eine Vermutung über die asymptotische Reihenentwicklung der Abbildung an einer analytischen Spitze. KW - Riemann mapping theorem KW - analytic cusp KW - asymptotic behaviour KW - boundary behaviour KW - Geometrische Funktionentheorie KW - Randverhalten KW - Riemannscher Abbildungssatz Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-3587 ER - TY - THES A1 - Hatzesberger, Simon T1 - Strongly Asymptotically Optimal Methods for the Pathwise Global Approximation of Stochastic Differential Equations with Coefficients of Super-linear Growth N2 - Our subject of study is strong approximation of stochastic differential equations (SDEs) with respect to the supremum and the L_p error criteria, and we seek approximations that are strongly asymptotically optimal in specific classes of approximations. For the supremum error, we prove strong asymptotic optimality for specific tamed Euler schemes relating to certain adaptive and to equidistant time discretizations. For the L_p error, we prove strong asymptotic optimality for specific tamed Milstein schemes relating to certain adaptive and to equidistant time discretizations. To illustrate our findings, we numerically analyze the SDE associated with the Heston–3/2–model originating from mathematical finance. KW - Stochastic differential equation KW - Strong approximation KW - Strong asymptotic optimality KW - Asymptotic lower error bounds KW - Asymptotic upper error bounds KW - Stochastische Differentialgleichung KW - Approximation Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-8100 ER - TY - THES A1 - Horáček, Jan T1 - Algebraic and Logic Solving Methods for Cryptanalysis N2 - Algebraic solving of polynomial systems and satisfiability of propositional logic formulas are not two completely separate research areas, as it may appear at first sight. In fact, many problems coming from cryptanalysis, such as algebraic fault attacks, can be rephrased as solving a set of Boolean polynomials or as deciding the satisfiability of a propositional logic formula. Thus one can analyze the security of cryptosystems by applying standard solving methods from computer algebra and SAT solving. This doctoral thesis is dedicated to studying solvers that are based on logic and algebra separately as well as integrating them into one such that the combined solvers become more powerful tools for cryptanalysis. This disseration is divided into three parts. In this first part, we recall some theory and basic techniques for algebraic and logic solving. We focus mainly on DPLL-based SAT solving and techniques that are related to border bases and Gröbner bases. In particular, we describe in detail the Border Basis Algorithm and discuss its specialized version for Boolean polynomials called the Boolean Border Basis Algorithm. In the second part of the thesis, we deal with connecting solvers based on algebra and logic. The ultimate goal is to combine the strength of different solvers into one. Namely, we fuse the XOR reasoning from algebraic solvers with the light, efficient design of SAT solvers. As a first step in this direction, we design various conversions from sets of clauses to sets of Boolean polynomials, and vice versa, such that solutions and models are preserved via the conversions. In particular, based on a block-building mechanism, we design a new blockwise algorithm for the CNF to ANF conversion which is geared towards producing fewer and lower degree polynomials. The above conversions allow usto integrate both solvers via a communication interface. To reach an even tighter integration, we consider proof systems that combine resolution and polynomial calculus, i.e. the two most used proof systems in logic and algebraic solving. Based on such a proof system, which we call SRES, we introduce new types of solving algorithms that demostrate the synergy between Gröbner-like and DPLL-like solving. At the end of the second part of the dissertation, we provide some experiments based on a new benchmark which illustrate that the our new method based on DPLL has the potential to outperform CDCL SAT solvers. In the third part of the thesis, we focus on practical attacks on various cryptograhic primitives. For instance, we apply SAT solvers in the case of algebraic fault attacks on the symmetric ciphers LED and derivatives of the block cipher AES. The main goal there is to derive so-called fault equations automatically from the hardware description of the cryptosystem and thus automatizate the attack. To give some extra power to a SAT solver that inverts the hash functions SHA-1 and SHA-2, we describe how to tweak the SAT solver using a programmatic interface such that the propagation of the solver and thus the attack itself is improved. KW - Boolean polynomial KW - Border basis KW - SAT solving KW - Combined proof system KW - Algebraic normal form KW - Conjunctive normal form KW - Algebraic fault attack KW - Kryptoanalyse KW - Polynom KW - Beweissystem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-7731 ER - TY - THES A1 - Fink, Thomas T1 - Curvature Detection by Integral Transforms N2 - In various fields of image analysis, determining the precise geometry of occurrent edges, e.g. the contour of an object, is a crucial task. Especially the curvature of an edge is of great practical relevance. In this thesis, we develop different methods to detect a variety of edge features, among them the curvature. We first examine the properties of the parabolic Radon transform and show that it can be used to detect the edge curvature, as the smoothness of the parabolic Radon transform changes when the parabola is tangential to an edge and also, when additionally the curvature of the parabola coincides with the edge curvature. By subsequently introducing a parabolic Fourier transform and establishing a precise relation between the smoothness of a certain class of functions and the decay of the Fourier transform, we show that the smoothness result for the parabolic Radon transform can be translated into a change of the decay rate of the parabolic Fourier transform. Furthermore, we introduce an extension of the continuous shearlet transform which additionally utilizes shears of higher order. This extension, called the Taylorlet transform, allows for a detection of the position and orientation, as well as the curvature and other higher order geometric information of edges. We introduce novel vanishing moment conditions which enable a more robust detection of the geometric edge features and examine two different constructions for Taylorlets. Lastly, we translate the results of the Taylorlet transform in R^2 into R^3 and thereby allow for the analysis of the geometry of object surfaces. KW - Curvature KW - Wavelet KW - Shearlet KW - Parabolic Radon transform KW - Edge classification KW - Krümmung KW - Wavelet-Transformation KW - Shearlet KW - Radon-Transformation KW - Konturfindung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-7684 ER - TY - THES A1 - Lorenz, Florian T1 - Analyse und Erzeugung von glatten Flächenübergängen für das CNC-Fräsen N2 - In dieser Arbeit werden numerisch stabile Methoden zur Prüfung von Stetigkeiten an Flächenübergängen vorgestellt und Algorithmen zur Erzeugung von G^2-stetigen Flächenübergängen hergeleitet. KW - Differentialgeometrie KW - B-Spline KW - Geometrische Modellierung KW - CNC-Maschine Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5166 ER - TY - THES A1 - Apfler, Sabine T1 - Erwerb mathematischer Kompetenzen in der Regelvolksschule N2 - Durch die Einführung der Bildungsstandardsüberprüfungen erhält die Frage nach der Kompetenzentwicklung von Kindern einen zentralen Stellenwert in Bildungsangelegenheiten. Lehrkräfte stehen dadurch vor der Aufgabe, ihren Unterricht diesbezüglich zu verändern und Lösungen zu finden. Die Frage, ob der Einsatz der Montessoripädagogik die Entwicklung mathematischer Kompetenzen positiv beeinflusst, wurde im Rahmen einer Dissertation diskutiert und empirisch erforscht werden. Der Arbeit liegt folgende Fragestellung zugrunde: Kann die Montessoripädagogik dazu beitragen, dass Schülerinnen und Schüler in österreichischen Regelvolksschulen ein hohes Kompetenzniveau in Mathematik erreichen? Wie unterscheidet sich die Kompetenzentwicklung in Klassen, die von Lehrpersonen mit beziehungsweise ohne Montessoriausbildung unterrichtet werden? Bei der vorliegenden Studie handelt es sich um eine Längsschnittuntersuchung mit zwei Testzeitpunkten. Im Sinne einer summativen Evaluation wurden zu Beginn der Untersuchung die Basiskompetenzen mit dem „Entwicklungsorientierten Test zur Erfassung mathematischer Basiskompetenzen ab Schuleintritt (MBK 1+)“ analysiert. Am Ende der dritten Schulstufe wurde eine abschließende Bewertung im Rahmen der IKM-Testung des BIFIE vorgenommen, um die Wirksamkeit des Einsatzes der Montessorimethode zu ermitteln. Untersucht wurden 14 Volksschulklassen, die entweder einer Untersuchungsgruppe oder einer Kontrollgruppe zugeordnet wurden. Die Klassen der Untersuchungsgruppe wurden von Lehrpersonen mit Montessori-Diplomausbildung unterrichtet, die Klassen der Kontrollgruppe von Lehrpersonen, die keine Montessoriausbildung absolviert haben. An der Studie nahmen 248 Schülerinnen und Schüler teil. Der Untersuchungszeitraum erstreckte sich über insgesamt drei Schuljahre. Die Ergebnisse der Studie zeigen Tendenzen, dass sich der Einsatz der Montessoripädagogik positiv auf die Kompetenzentwicklung der Kinder im Bereich der Mathematik auswirkt. KW - Montessori KW - Mathematik KW - Kompetenzen KW - Österreich KW - Regelschule KW - Mathematikunterricht KW - Montessori-Pädagogik KW - Längsschnittuntersuchung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5593 ER - TY - THES A1 - Klaus, Tina T1 - Complexity Analysis of Quantizations of Multidimensional Stochastic Differential Equations N2 - The dissertation is located in the field of quantizations of certain stochastic processes, namely a solution X of a multidimensional stochastic differential equation (SDE). The quantization problem for X consists in approximating X by a a random element which takes only finitely many values. Our main interest lies in the investigation of the asymptotic behavior of the Nth minimal quantization error of X as N tends to infinity, which incorporates the determination of both the sharp rate of convergence and explicit asymptotic constants. Especially explicit asymptotic constants have been so far unknown in the context of multidimensional SDEs. Furthermore, as part of our analysis, we provide a method which yields a strongly asymptotically optimal sequence of N-quantization of X. In certain special cases our method is fully constructive and the algorithm is easy to implement. KW - Stochastische Differentialgleichung KW - Komplexität KW - Quantifizierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-7665 ER - TY - THES A1 - Stadler, Thomas T1 - Eine Anwendung der Invariantentheorie auf das Korrespondenzproblem lokaler Bildmerkmale N2 - Als sich in der ersten Hälfte des 19. Jahrhunderts zunehmend mehr bedeutende Mathematiker mit der Suche nach Invarianten beschäftigten, konnte natürlich noch niemand vorhersehen, dass die Invariantentheorie mit Beginn des Computerzeitalters in der Bildverarbeitung bzw. dem Rechnersehen ein äußerst fruchtbares Anwendungsgebiet finden wird. In dieser Arbeit wird eine neue Anwendungsmöglichkeit der Invariantentheorie in der Bildverarbeitung vorgestellt. Dazu werden lokale Bildmerkmale betrachtet. Dabei handelt es sich um die Koordinaten einer Polynomfunktion bzgl. einer geeigneten Orthonormalbasis von P_n(R^2,R), die die zeitintegrierte Sensorinputfunktion auf lokalen Pixelfenstern bestmöglich approximiert. Diese Bildmerkmale werden in vielen Anwendungen eingesetzt, um Objekte in Bildern zu erkennen und zu lokalisieren. Beispiele hierfür sind die Detektion von Werkstücken an einem Fließband oder die Verfolgung von Fahrbahnmarkierungen in Fahrerassistenzsystemen. Modellieren lässt sich die Suche nach einem Muster in einem Suchbild als Paar von Stereobildern, auf denen lokal die affin-lineare Gruppe AGL(R) operiert. Will man also feststellen, ob zwei lokale Pixelfenster in etwa Bilder eines bestimmten dreidimensionalen Oberflächenausschnitts sind, ist zu klären, ob die Bildausschnitte durch eine Operation der Gruppe AGL(R) näherungsweise ineinander übergeführt werden können. Je nach Anwendung genügt es bereits, passende Untergruppen G von AGL(R) zu betrachten. Dank der lokalen Approximation durch Polynomfunktionen induziert die Operation einer Untergruppe G eine Operation auf dem reellen Vektorraum P_n(R^2,R). Damit lässt sich das Korrespondenzproblem auf die Frage reduzieren, ob es eine Transformation T in G gibt so, dass p ungefähr mit der Komposition von q und T für die zugehörigen Approximationspolynome p,q in P_n(R^2,R) gilt. Mit anderen Worten, es ist zu klären, ob sich p und q näherungsweise in einer G-Bahn befinden, eine typische Fragestellung der Invariantentheorie. Da nur lokale Bildausschnitte betrachtet werden, genügt es weiter, Untergruppen G von GL_2(R) zu betrachten. Dann erhält man sofort auch die Antwort für das semidirekte Produkt von R^2 mit G. Besonders interessant für Anwendungen ist hierbei die spezielle orthogonale Gruppe G=SO_2(R) und damit insgesamt die eigentliche Euklidische Gruppe. Für diese Gruppe und spezielle Pixelfenster ist das Korrespondenzproblem bereits gelöst. In dieser Arbeit wird das Problem in eben dieser Konstellation ebenfalls gelöst, allerdings auf elegante Weise mit Methoden der Invariantentheorie. Der Ansatz, der hier vorgestellt wird, ist aber nicht auf diese Gruppe und spezielle Pixelfenster begrenzt, sondern leicht auf weitere Fälle erweiterbar. Dazu ist insbesondere zu klären, wie sich sogenannte fundamentale Invarianten von lokalen Bildmerkmalen, also letztendlich Invarianten von Polynomfunktionen, berechnen lassen, d.h. Erzeugendensysteme der entsprechenden Invariantenringe. Mit deren Hilfe lässt sich die Zugehörigkeit einer Polynomfunktion zur Bahn einer anderen Funktion auf einfache Weise untersuchen. Neben der Vorstellung des Verfahrens zur Korrespondenzfindung und der dafür notwendigen Theorie werden in dieser Arbeit Erzeugendensysteme von Invariantenringen untersucht, die besonders "schöne" Eigenschaften besitzen. Diese schönen Erzeugendensysteme von Unteralgebren werden, analog zu Gröbner-Basen als Erzeugendensysteme von Idealen, SAGBI-Basen genannt ("Subalgebra Analogs to Gröbner Bases for Ideals"). SAGBI-Basen werden hier insbesondere aus algorithmischer Sicht behandelt, d.h. die Berechnung von SAGBI-Basen steht im Vordergrund. Dazu werden verschiedene Algorithmen erarbeitet, deren Korrektheit bewiesen und implementiert. Daraus resultiert ein Software-Paket zu SAGBI-Basen für das Computeralgebrasystem ApCoCoA, dessen Funktionalität in diesem Umfang in keinem Computeralgebrasystem zu finden sein wird. Im Zuge der Umsetzung der einzelnen Algorithmen konnte außerdem die Theorie der SAGBI-Basen an zahlreichen Stellen erweitert werden. KW - Computeralgebra KW - SAGBI-Basen KW - Invariantentheorie KW - Bildverarbeitung KW - (lokale) Bildmerkmale Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4026 ER - TY - THES A1 - Sipal, Bilge T1 - Border Basis Schemes N2 - The basic idea of border basis theory is to describe a zero-dimensional ring P/I by an order ideal of terms whose residue classes form a K-vector space basis of P/I. The O-border basis scheme is a scheme that parametrizes all zero-dimensional ideals that have an O-border basis. In general, the O-border basis scheme is not an affine space. Subsequently, in [Huib09] it is proved that if an order ideal with "d" elements is defined in a two-dimensional polynomial ring and it is of some special shapes, then the O-border basis scheme is isomorphic to the affine space of dimension 2d. This thesis is dedicated to find a more general condition for an O-border basis scheme to be isomorphic to an affine space of dimension "nd" that is independent of the shape of the order ideal with "d" elements and "n" is the dimension of the polynomial ring that the order ideal is defined in. We accomplish this in 6 Chapters. In Chapters 2 and 3 we develop the concepts and properties of border basis schemes. In Chapter 4 we transfer the smoothness criterion (see [Huib05]) for the point (0,...,0) in a Hilbert scheme of points to the monomial point of the border basis scheme by employing the tools from border basis theory. In Chapter 5 we explain trace and Jacobi identity syzygies of the defining equations of a O-border basis scheme and characterize them by the arrow grading. In Chapter 6 we give a criterion for the isomorphism between 2d dimensional affine space and O-border basis scheme by using the results from Chapters 3 and Chapter 4. The techniques from other chapters are applied in Chapter 6.1 to segment border basis schemes and in Chapter 6.2 to O-border basis schemes for which O is of the sawtooth form. KW - Border Bases, Border Basis Scheme, Monomial point, Cotangent Space, Hilbert Schemes KW - Polynomring KW - Basis (Mathematik) KW - Kommutative Algebra, Randbasen, Randbasen Schema Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4702 ER - TY - THES A1 - Handeck, Jörg T1 - Analyse und Korrektur von Teileprogrammen für numerisch gesteuerte Werkzeugmaschinen N2 - Splinekurven sind oft das erste Mittel der Wahl, wenn Daten interpoliert oder approximiert werden sollen. Sie spielen in vielen praktischen Anwendungsbereichen eine wichtige Rolle und sind in Bereichen des CAD/CAM nicht mehr weg zu denken. In der vorliegenden Arbeit werden in diesem Kontext Bahnpunkte zur Steuerung von Werkzeugmaschinen untersucht. Die Analyse wird mit Hilfe eines Multiresolution (MRA) Ansatzes für Splinekurven mit adaptiven Knotenfolgen realisiert. Dieser MRA Ansatz basiert auf einer Least-Squares-Projektion zum Knotenentfernen und unterscheidet sich somit zu bekannten Ansätzen, die auf orthogonalen Komplementen aufbauen. Des Weiteren wird ein Konzept zur Approximation von Orientierungsdaten mittels homogenen Quaternionensplines vorgestellt. Diese Splines leben auf der Sphäre und lassen sich mittels Knotenentfernen bzw. einfügen verfeinern. Somit lässt sich das vorgestellte MRA–Analyseverfahren ebenfalls auf diese Kurven anwenden. Weiter konnte für diese Kurven eine konvexe Hülle–Eigenschaft nachgewiesen werden. KW - Spline MRA KW - Spline KW - Numerische Steuerung KW - Werkzeugmaschine Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4546 ER - TY - THES A1 - Pfeffer, Wolfgang T1 - Qualitative Entwicklung der Begriffsbildung im Fach Mathematik in der Studieneingangsphase N2 - Der Übergang vom sekundären zum tertiären Bildungsbereich im Fach Mathematik stellt in den vergangenen Jahren ein zentrales Forschungsinteresse der mathematikdidaktischen Forschung dar. Das Forschungsfeld macht hierbei drei grundlegende Bedingungsfaktoren aus: epistemologische und kognitive, soziologische und kulturelle sowie didaktische Schwierigkeiten. Der Schwerpunkt der vorliegenden Arbeit liegt auf dem ersten Bereich, der den sich wandelnden Charakter der Mathematik inkludiert. Für viele Studienanfängerinnen und -anfänger ist der Wechsel von der Schule zur Universität "traumatisch", da sich das Anforderungsprofil an der Hochschule doch deutlich von dem bisher Gewohnten abhebt. Gerade die Studieneingangsphase ist für den späteren Studienerfolg als wichtigster Abschnitt anzusehen; werden die vielfach vorhandenen fachlichen Defizite sowie falschen Vorstellungen nicht beseitigt, führt dies oft zu einem vorzeitigen Studienabbruch. Untersuchungen zur mathematischen Begriffsbildung über einen längeren Zeitraum im Verlauf eines Hochschulstudiums fehlen bislang. Hieraus ergibt sich die Motivation für das in dieser Arbeit beschriebene Forschungsprojekt, das sich in drei Teile gliedert. Der erste Teil fasst den Stand der Forschung zum Übergang Schule -- Hochschule im Fach Mathematik zusammen. Der Fokus richtet sich dabei auf den sich wandelnden Charakter der Mathematik sowie die unterschiedlichen Anforderungen in Bezug auf die Begriffsbildung. Der zweite Teil stellt mathematisches Vorwissen als möglichen Bedingungsfaktor für den Studienerfolg dar und beschreibt anschließend Konzeption, Auswertung sowie die Diskussion der Ergebnisse eines Fragebogens zum Hintergrundwissen Mathematik. Der dritte Teil der Arbeit beschreibt eine qualitative und längsschnittlich durchgeführte, leitfadengestützte Interviewstudie, in deren Rahmen die gleiche Stichprobe im Laufe der ersten beiden Semester zu drei unterschiedlichen Zeitpunkten befragt wurde. Im Hinblick auf die praktische Relevanz für die Lehre wurden anhand der Äußerungen der Studierenden Fehlvorstellungen hinsichtlich der mathematischen Konzepte identifiziert und kategorisiert. Weiter wird eine Klassifikation der studentischen Vorstellungen hinsichtlich deren wissenschaftlichen Qualität vorgenommen sowie die Entwicklung dieser über die drei Interviewzeitpunkte hinweg beschrieben. Die Ergebnisse der Arbeit zeigen einerseits massive Defizite der Studienanfängerinnen und -anfänger in Kenntnissen und Fertigkeiten mathematischen Grundwissens. Darüber hinaus erfolgt auch die Begriffsbildung resp. -entwicklung hinsichtlich zentraler mathematischer Konzepte der Hochschulmathematik auf sehr niedrigem Niveau. Als Indiz hierfür zeugen die vielfältig identifizierten Fehlvorstellungen, die sich über alle Interviewzeitpunkte hinweg zeigten. Hieraus resultiert eine verstärkte Notwendigkeit der Förderung der Begriffsbildung sowie -entwicklung in der Studieneingangsphase. KW - Übergang Schule - Hochschule KW - Concept Image KW - Concept Definition KW - Begriffsbildung KW - Kognitives Schema KW - Mathematikstudium KW - Studienanfang Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4948 ER - TY - THES A1 - Ruppert, Julia T1 - Asymptotic Expansion for the Time Evolution of the Probability Distribution Given by the Brownian Motion on Semialgebraic Sets N2 - In this thesis, we examine whether the probability distribution given by the Brownian Motion on a semialgebraic set is definable in an o-minimal structure and we establish asymptotic expansions for the time evolution. We study the probability distribution as an example for the occurrence of special parameterized integrals of a globally subanalytic function and the exponential function of a globally subanalytic function. This work is motivated by the work of Comte, Lion and Rolin, which considered parameterized integrals of globally subanalytic functions, of Cluckers and Miller, which examined parameterized integrals of constructible functions, and by the work of Cluckers, Comte, Miller, Rolin and Servi, which treated oscillatory integrals of globally subanalytic functions. In the one dimensional case we show that the probability distribution on a family of sets, which are definable in an o-minimal structure, are definable in the Pfaffian closure. In the two-dimensional case we investigate asymptotic expansions for the time evolution. As time t approaches zero, we show that the integrals behave like a Puiseux series, which is not necessarily convergent. As t tends towards infinity, we show that the probability distribution is definable in the expansion of the real ordered field by all restricted analytic functions if the semialgebraic set is bounded. For this purpose, we apply results for parameterized integrals of globally subanalytic functions of Lion and Rolin. By establishing the asymptotic expansion of the integrals over an unbounded set, we demonstrate that this expansion has the form of convergent Puiseux series with negative exponents and their logarithm. Subsequently, we get that the asymptotic expansion is definable in an o-minimal structure. Finally, we study the three-dimensional case and give the proof that the probability distribution given by the Brownian Motion behaves like a Puiseux series as time t tends towards zero. As t approaches infinity and the semialgebraic set is bounded, it can be ascertained that the probability distribution has the form of a constructible function by results of Cluckers and Miller and therefore it is definable in an o-minimal structure. If the semialgebraic set is unbounded, we establish the asymptotic expansions and prove that the probability distribution given by the Brownian Motion on unbounded sets has an asymptotic expansion of the form of a constructible function. In consequence of that, the asymptotic expansion is definable in an o-minimal structure. KW - o-minimality KW - asymptotic expansions KW - globally subanalytic sets KW - exponential parameterized integrals KW - Brownian Motion KW - Brownsche Bewegung KW - O-Minimalität KW - Asymptotische Entwicklung Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5069 ER - TY - THES A1 - Gütschow, Silja T1 - Roulets - Eine Integraltransformation zur Bestimmung gerichteter Singularitäten N2 - In dieser Arbeit wird eine neue Integraltransformation, die Roulettransformation, eingeführt. Diese arbeitet mit anisotropen Skalierungen und Rotationen. Es wird gezeigt, dass die Roulettransformation allgemeine gerichtete Singularitäten im Sinne von temperierten Distributionen auflöst. Die Abklingraten an Punkt- sowie Liniensingularitäten werden explizit angegeben. KW - Integraltransformation KW - Singularität Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5929 ER - TY - THES A1 - Kell, Christian T1 - A Structure-based Attack on the Linearized Braid Group-based Diffie-Hellman Conjugacy Problem in Combination with an Attack using Polynomial Interpolation and the Chinese Remainder Theorem N2 - This doctoral thesis is dedicated to improve a linear algebra attack on the so-called braid group-based Diffie-Hellman conjugacy problem (BDHCP). The general procedure of the attack is to transform a BDHCP to the problem of solving several simultaneous matrix equations. A first improvement is achieved by reducing the solution space of the matrix equations to matrices that have a specific structure, which we call here the left braid structure. Using the left braid structure the number of matrix equations to be solved reduces to one. Based on the left braid structure we are further able to formulate a structure-based attack on the BDHCP. That is to transform the matrix equation to a system of linear equations and exploiting the structure of the corresponding extended coefficient matrix, which is induced by the left braid structure of the solution space. The structure-based attack then has an empirically high probability to solve the BDHCP with significantly less arithmetic operations than the original attack. A third improvement of the original linear algebra attack is to use an algorithm that combines Gaussian elimination with integer polynomial interpolation and the Chinese remainder theorem (CRT), instead of fast matrix multiplication as suggested by others. The major idea here is to distribute the task of solving a system of linear equations over a giant finite field to several much smaller finite fields. Based on our empirically measured bounds for the degree of the polynomials to be interpolated and the bit size of the coefficients and integers to be recovered via the CRT, we conclude an improvement of the run time complexity of the original algorithm by a factor of n^8 bit operations in the best case, and still n^6 in the worst case. KW - Linear algebra attack KW - Braid group-based cryptography KW - Row echelon form calculation using polynomial interpolation and the chinese remainder theorem KW - Diffie-Hellman conjugacy problem KW - Kryptologie KW - Zopfgruppe KW - Diffie-Hellman-Algorithmus Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-6476 ER - TY - THES A1 - Tueno, Anselme T1 - Multiparty Protocols for Tree Classifiers N2 - Cryptography is the scientific study of techniques for securing information and communication against adversaries. It is about designing and analyzing encryption schemes and protocols that protect data from unauthorized reading. However, in our modern information-driven society with highly complex and interconnected information systems, encryption alone is no longer enough as it makes the data unintelligible, preventing any meaningful computation without decryption. On the one hand, data owners want to maintain control over their sensitive data. On the other hand, there is a high business incentive for collaborating with an untrusted external party. Modern cryptography encompasses different techniques, such as secure multiparty computation, homomorphic encryption or order-preserving encryption, that enable cloud users to encrypt their data before outsourcing it to the cloud while still being able to process and search on the outsourced and encrypted data without decrypting it. In this thesis, we rely on these cryptographic techniques for computing on encrypted data to propose efficient multiparty protocols for order-preserving encryption, decision tree evaluation and kth-ranked element computation. We start with Order-preserving encryption (OPE) which allows encrypting data, while still enabling efficient range queries on the encrypted data. However, OPE is symmetric limiting, the use case to one client and one server. Imagine a scenario where a Data Owner (DO) outsources encrypted data to the Cloud Service Provider (CSP) and a Data Analyst (DA) wants to execute private range queries on this data. Then either the DO must reveal its encryption key or the DA must reveal the private queries. We overcome this limitation by allowing the equivalent of a public-key OPE. Decision trees are common and very popular classifiers because they are explainable. The problem of evaluating a private decision tree on private data consists of a server holding a private decision tree and a client holding a private attribute vector. The goal is to classify the client’s input using the server’s model such that the client learns only the result of the classification, and the server learns nothing. In a first approach, we represent the tree as an array and execute only d interactive comparisons (instead of 2 d as in existing solutions), where d denotes the depth of the tree. In a second approach, we delegate the complete tree evaluation to the server using somewhat or fully homomorphic encryption where the ciphertexts are encrypted under the client’s public key. A generalization of a decision tree is a random forest that consists of many decision trees. A classification with a random forest evaluates each decision tree in the forest and outputs the classification label which occurs most often. Hence, the classification labels are ranked by their number of occurrences and the final result is the best ranked one. The best ranked element is a special case of the kth-ranked element. In this thesis, we consider the secure computation of the kth-ranked element in a distributed setting with applications in benchmarking and auctions. We propose different approaches for privately computing the kth-ranked element in a star network, using either garbled circuits or threshold homomorphic encryption. KW - Mathematik KW - Kryptologie Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-8251 ER - TY - THES A1 - Tran, Nguyen Khanh Linh T1 - Kaehler Differential Algebras for 0-Dimensional Schemes and Applications N2 - The aim of this dissertation is to investigate Kaehler differential algebras and their Hilbert functions for 0-dimensional schemes in P^n. First we give relations between Kaehler differential 1-forms of fat point schemes and another fat point schemes. Then we determine the Hilbert polynomial and give a sharp bound for the regularity index of the module of Kaehler differential m-forms, for 0