|
|
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.
|
|
|
Application of Multilinear Forms in Cryptography
Rabas, Tomáš ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.
|
|
|
Elliptic curves over finite fields
Beran, Adam ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis, we study the theory of elliptic curves, with the main focus on elliptic curves over finite fields. We present basic theory, taking several technical aspects into consideration (singularity of the curve, effect of field characteristic on the form of the equation of elliptic curve). We algebraically deduce and formulate the group law, that is the definition of addition on a set of points on elliptic curve). We prove a known result saying that the set of points on elliptic curve under addition forms a group. We present an elementary proof, some of the calculations will be carried out in computer program Mathematica due to their complexity. Finally, we study endomorphisms of elliptic curves over finite fields (homomorphisms on the set of points on elliptic curve that are defined by rational functions). Using obtained results, we prove the Hasse's theorem, which provides an estimate of the order of the group of points on elliptic curve over finite field. 1
|
|
|
Multilinear Maps Over the Integers
Havránek, František ; Žemlička, Jan (advisor) ; Šaroch, Jan (referee)
The thesis aims to describe the [CLT15] scheme, which is based on the Diffie- Hellman scheme and uses multilinear maps over integers. This scheme enables an exchange of a key among several participants. The level κ scheme (using a κ-linear map) enables the exchange of a key among κ + 1 participants. The thesis introduces the basic terms, describes the needed theory, the base of which is the Chinese Remainder Theorem, and also the preparation and usage of the scheme. The correctness of the scheme is proved as well and the related requirements on the basic parameters are discussed.
|
guest ::
RSS feed.