
Multiplication in a finite field of characteristic 2 and XORmetrics
Carulkov, Nikita Edward ; Žemlička, Jan (advisor) ; Göloglu, Faruk (referee)
XORcounts measure the efficiency of multiplication in finite fields of characteristic 2. In the first chapter we define two XORcounts (the direct XORcount and the sequential XORcount) and present detailed proofs of some propositions from the paper from Lukas Kolsch about the XORcounts of inverse matrices and permutation similar matrices. It seems that the case when the direct XORcount is lower than the sequential XORcount is rare. We will explore those cases in the second chapter. Some of them were already described in the paper from Lukas Kolsch and we prove that they occur only for matrices with order higher or equal to six. 1


Linear version of Holub's algorithm
Tvrdý, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a stepbystep visualization for particular input words. 1


Generalized integral property
Hrúzová, Jana ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis is based on an article C. Boura and A. Canteaut, Another View of the Division Property, which is focused on division property of sets from Fn 2 . In this thesis we introduce important definitions and propositions about boolean function, polynomials and ReedMuller codes at the beginning. Then we define parity set of a set from Fn 2 , which helps us to simplify the division property. We also show how sets, which satisfy division property of certain order, look like. From that we could follow how the division property propagate through the substitutionpermutation network. 1


Testing the projectivity of modules
Matoušek, Cyril ; Šaroch, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis, we study the problem of the existence of test modules for the projectivity. A right Rmodule is said to be a test module if it holds for every right Rmodule M that M is projective whenever T ∈ M⊥ . We show that test modules exist over right perfect rings, although their existence is not provable in ZFC in case of nonright perfect rings. In order to prove this, we use Shelah's uni formization principle, which is independent of the axioms of ZFC. Furthermore, we show that test modules exist over rings of finite global dimension assuming the weak diamond principle, which is also independent of ZFC. 1


Rational linear dependencies of periodic points of the logistic map
Mik, Matěj ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
Periodn points of a polynomial f are roots, and hence elements of the splitting field, of the polynomial fn (x) − x, where fn denotes the nth iterate of f. In the thesis, we will focus on describing rational linear dependencies of periodn points of the polynomial f(x) = 4x(1 − x), which defines the socalled logistic map. We will present a description of the dependencies for n = 1, . . . , 5 and a partial result for n = 6. We will be using computer calculated factorizations of polynomials over rational numbers and some finite field extensions. The factorizations will give us coordinates of the periodic points relative to some basis of their linear span, which will allow us to use a simple way of describing their dependencies. In the end of the thesis, we will put together an algorithm for describing the dependencies for a general n.


Short invertible elements in cyclotomic rings
Kroutil, Jaroslav ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This bachelor's thesis is based on an article about the criterion for invertibility of elements in special chosen cyclotomic rings. In this thesis, we start with defining important terms and statements from algebra that we need. Then we will deal with the existence of infinitely many prime numbers which satisfy conditions that are used for irreducible decomposition of cyclotomic polynomials. Based on this polynomials we define cyclotomic rings and at the end of this thesis we prove invertibility of elements from this rings depending on the size of their norm.


Modules over string algebras
Löwit, Jakub ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
The aim of this thesis is to investigate the categories of modules over the so called string algebras. In particular, we try to understand the cotorsion pairs in these categories, which boils down to understanding the decompositions of extensions of such modules. For string algebras with some oriented tree for the underlying quiver, we describe some classes given by these cotorsion pairs in terms of purely combinatorial closure properties. For any string algebras, the combinatorics appears to be similar, althought more complicated.


LWE and provably secure key exchange schemes
Václavek, Jan ; Příhoda, Pavel (advisor) ; Žemlička, Jan (referee)
The threat of largescale quantum computers motivates cryptographers to base cryptosystems on problems believed to be resistant against quantum computers. In this thesis, we focus on the LWE problem which is believed to be resistant against quantum computers. First, we describe lattices which are closely related to the LWE problem. We introduce basic notions, describe lattice problems and solve exercises related to the covering radius of lattice. After that, we introduce the LWE problem and its variants. We prove reductions from two lattice problems to certain variant of the LWE problem. We define the notion of statistical distance and prove some lemmata about it which we need within reductions. Moreover, we show concrete application of the LWE problem. We describe a scheme for key exchange and briefly prove its security under the assumption that the LWE problem is hard. 1


Proving security of hash functions
Zpěváček, Marek ; Příhoda, Pavel (advisor) ; Žemlička, Jan (referee)
This thesis focuses on proof of reduction from approximate SBP to SIS. The proof was already accomplished by Mikl'os Ajtai in 1996 in his groun dbreaking work, however his proof lacks level of detail. The reduction is worstcase to averagecase and no reduction of this type was known prior to the Ajtai's one. That is the reason why we found appropriate to return to the proof and provide it in more detailed form. Furthermore, the complexity of basic lattice problems is summarized. Based on these complexities and proven reduction, it is possible to define collisionresistant hash functions. This work is also briefly focused on such functions. 1


Max rings
Beneš, Daniel ; Žemlička, Jan (advisor) ; Šaroch, Jan (referee)
Topic of this thesis is max rings, which are the rings, whose nonzero modu les have maximal submodules. At the begining we prove a characterization of commutative max rings as rings with Tnilpotent Jacobson radical and von Ne umann regular factor ring of the Jacobson radical. Our next concern are group rings, where we describe all commutative group rings, that are max. These are the group rings, that are composed from a commutative max ring and an abelian torsion group, where is finitely many elements of order pn for p not invertible in the ring. Finally we use this characterization to construct noncommutative group rings, which are max but not perfect.
