|
|
Applications of Gröbner bases in cryptography
Fuchs, Aleš ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
Title: Applications of Gröbner bases in cryptography Author: Aleš Fuchs Department: Department of Algebra Supervisor: Mgr. Jan Št'ovíček Ph.D., Department of Algebra Abstract: In the present paper we study admissible orders and techniques of multivariate polynomial division in the setting of polynomial rings over finite fields. The Gröbner bases of some ideal play a key role here, as they allow to solve the ideal membership problem thanks to their properties. We also explore features of so called reduced Gröbner bases, which are unique for a particular ideal and in some way also minimal. Further we will discuss the main facts about Gröbner bases also in the setting of free algebras over finite fields, where the variables are non-commuting. Contrary to the first case, Gröbner bases can be infinite here, even for some finitely generated two- sided ideals. In the last chapter we introduce an asymmetric cryptosystem Polly Cracker, based on the ideal membership problem in both commutative and noncommutative theory. We analyze some known cryptanalytic methods applied to these systems and in several cases also precautions dealing with them. Finally we summarize these precautions and introduce a blueprint of Polly Cracker reliable construction. Keywords: noncommutative Gröbner bases, Polly Cracker, security,...
|
|
|
Group rings in coding theory
Horáček, Jan ; Žemlička, Jan (advisor) ; Šťovíček, Jan (referee)
This work is focused on linear error-correcting codes in group rings. The basic introduc- tion to group rings and to coding in group rings is given. By code we mean a R-submodul, which generalizes the definition of the code as an ideal. We describe unit-derived and zero- divisor codes. We test paramaters of unit-derived codes. The construction of LDPC codes without short cycles is explained. Except from the derivation of the generator and check matrix we focus on algebraic properties of codes and group rings. We also deal with the self-dual codes, reversible codes or number of units in a finite group algebra of a cyclic group. 1
|
|
|
Gröbner bases
Petržilková, Lenka ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we remind you of the basic Buchberger algorithm for com- puting the Gröbner base over commutative polynomial rings. We also observe uniqueness of the Gröbner base for the ideal. Next we research less known, but more effective (for some instances) Faugère F4 algorithm. At the end of the first chapter we compare these two algorithms. In the second chapter we analyze a generalization of the Buchberger algorithm for noncommutative rings both for free algebra and factor algebra. On the contary to the commu- tative case, Gröbner bases can be infinite in this case, even for some finitely generated ideals. Among other things, we investigate quasi-zero elements,i.e. such elements, that we get zero by multiplying them with an arbitrary term, and their role in the division of a polynom by set of polynoms. 1
|
|
|
Set-theoretic methods in module theory
Slávik, Alexander ; Trlifaj, Jan (advisor) ; Žemlička, Jan (referee)
A class of modules is called deconstructible if it coincides with the class of all S-filtered modules for some set of modules S. Such classes provide a convenient setting for construction of approximations. We prove that for any deconstructible class C the class of all modules possessing a C-resolution is deconstructible and the same holds for the classes of mod ules with bounded C-resolution dimension. Furthermore, we study the lo cally F-free modules; a sufficient condition on the class F is given for the class of all locally F-free modules to be closed under transfinite exten sions. This enables us to show that there are many non-trivial examples of non-deconstructible classes, generalizing the recent result of D. Herbera and J. Trlifaj concerning the non-deconstructibility of the class of all flat Mittag-Leffler modules over a non-right perfect ring.
|
|
|
Description of the cryptosystem HFE
Jančaříková, Irena ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This bachelor thesis deals with the description of the assymetric HFE cryptosystem. This thesis contains encryption and decryption using this cryptosystem, estimations of the time complexity of private and public transformation and the memory requirements to store secret and public keys. Thesis also contains a basic description of the predecessor HFE cryptosystem, cryptosystem C *. The work includes a short passage about MQ problem, which are cryptosystems based on and a short treatise on finite fields over which cryptosystems are both defined. The paper deals with the attack, which proves possibility of breaking C * for the majority of encrypted messages and contains a variant of this attack for HFE cryptosystem.
|
|
| |
|
|
Solving systems of equations over commutative rings
Seidl, Jan ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
The object of this work is to offer algorithm how can be solved systems of linear equations Ax=b over principal ideal rings. We prove that for every nonzero matrix over principal ideal rings there exists its Smith form. Using Smith form we transform the system of equations to simple diagonal form and we show how we can obtain the solution of the original system from its diagonal form. Whole procedure we demonstrate by the examples over Z, Zm and Q[x]. Thereafter we show how is possible to implement the algorithm for these rings by using software Mathematica. The work should provide procedure according to which shold not be difficult to modify algorithm to gain solution over another rings. 1
|
|
|
Kompaktní objekty v kategoriích modulů
Kálnai, Peter ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
Title: Compact objects in categories of modules Author: Peter Kálnai Department: Department of Algebra Supervisor: Mgr. Jan Žemlička, Ph.D., Department of Algebra Abstract: In the thesis we state baic properties of compact objects in various appropriate categories like categories of modules, stable factor category over a perfect ring and Grothendieck categories. We find a ring R such that the class of dually slender R-modules is closed under direct products under some set-theoretic assumption. Finally, we characterize the conditions, when countably generat- ed projective modules are finitely generated, expressed by their Grothendieck monoid. Keywords: compact, dually slender module, stable module category, projective module, self-small
|
|
| |
|
| |
guest ::
