@phdthesis{Ullah2012, author = {Ullah, Ehsan}, title = {New Techniques for Polynomial System Solving}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26815}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {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{\"o}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.}, subject = {Polynoml{\"o}sung}, language = {en} } @phdthesis{Xiu2012, author = {Xiu, Xingqiang}, title = {Non-commutative Gr{\"o}bner Bases and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26827}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Commutative Gr{\"o}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{\"o}bner bases also have many useful properties. However, applications of non-commutative Gr{\"o}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{\"o}bner bases and investigate the applications of non-commutative Gr{\"o}bner bases. Gr{\"o}bner basis theory in free monoid rings was carefully revised and Gr{\"o}bner bases were precisely characterized in great detail. For the computations of Gr{\"o}bner bases, the Buchberger Procedure was formulated. Three methods, say interreduction on obstructions, Gebauer-M{\"o}ller criteria, and detecting redundant generators, were developed for efficiently improving the Buchberger Procedure. Further, the same approach was applied to study Gr{\"o}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{\"o}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{\"o}bner basis computations and many concrete applications. The package gbmr and a collection of interesting examples are available at http://www.apcocoa.org/.}, subject = {Gr{\"o}bner-Basis}, language = {en} }