|
|
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 step-by-step 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 Reed-Muller 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 substitution-permutation 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 R-module is said to be a test module if it holds for every right R-module 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 non-right 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)
Period-n 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 period-n points of the polynomial f(x) = 4x(1 − x), which defines the so-called 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 large-scale 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 worst-case to average-case 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 collision-resistant 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 T-nilpotent 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.
|
|
|
Algorithms for the computation of Galois groups
Kubát, David ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
This thesis covers the topic of the computation of Galois groups over the rationals. Beginning with the classic algorithm by R. Stauduhar, we then review the theory necessary to explain the modular algorithm by K. Yokoyama. More precisely, we discuss the notion of the universal splitting ring of a polynomial. For a separable polynomial, we then study idempotents in the universal splitting ring. The modular algorithm involves computations in the ring of p-adic integers. Examples are given for polynomials of degree 3 and 4.
|
guest ::
RSS feed.