|
|
Binary codes induced by the line graph of an n-dimensional cube
Janovský, Tomáš ; Žemlička, Jan (advisor) ; Šťovíček, Jan (referee)
This paper deals with the binary codes from the line graph of the n-cube, then the codes of the design, which is defined by the vertex graph of the n-cube, and finally the dual codes of these codes. The first chapter is devoted to an introduction to the topic and the necessary concepts from the theory of linear codes, graphs and designs are defined there. The second chapter is devoted to the construction of the aforementioned codes, the description of their basic parameters such as the dimension and the Hamming distance of the code, and finally the description of the generating matrices of these codes. Finally, the last chapter deals with the dual codes of the codes constructed in the second chapter especially again the description of the Hamming distance.
|
|
| |
|
| |
|
|
Edwards curves and elliptic function fields
Beran, Adam ; Drápal, Aleš (advisor) ; Žemlička, Jan (referee)
In this thesis, we study twisted Edwards curves using the theory of algebraic function fields. After summarizing the basic theory, we focus on the structure of the function field for curves that are given by an equation of the form x2 2 = f(x1), where f is a monic polynomial of degree four. We show that twisted Edwards curves correspond to a special case when f(x1) = g(x2 1), where g is a quadratic polynomial with two distinct nonzero roots. We describe the basic properties of twisted Edwards curves, with special attention given to possible places at infinity. Next, we derive formulas for the point addition, which is achieved by using the relation between points on the curve, places of degree one and elements of the Picard group. Furthermore, we summarize how the point addition can be interpreted geometrically, and outline several alternative coordinate systems based on projective coordinates. Finally, we present two examples of twisted Edwards curves that are nowadays being used in cryptographic applications. 1
|
|
|
Secure multi-party computation modulo p^k
Struk, Martin ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
The thesis deals with a subfield of cryptography called secure multi-party computation which is a technique that allows multiple parties to work together to compute a single function while preserving the privacy of it's inputs. More specifically, the thesis deals with secure multi-party computation over the ring of integers modulo pk . The thesis begins with an introduction of the general principle of secure multi-party protocols, followed by the construction of the necessary theoretical groundwork over commutative rings, wich will be needed to describe and understand a specific protocol in the last section of the thesis. 1
|
|
|
MDS matrices
Vlášková, Šárka ; Žemlička, Jan (advisor) ; Patáková, Zuzana (referee)
MDS matrices are widely used in coding theory and cryptography (e.g. in diffusion layers of block ciphers or hash functions), but the construction of MDS matrices is not at all trivial, especially when we require some other suitable properties (involution, efficiency of implementation). That is why we will deal with the construction of MDS matrices (with other properties) in this thesis. We will show a construction of MDS matrices based on Cauchy matrices and on Vandermonde matrices. Then we will present an algorithm for testing whether a given matrix is MDS. And finally, we will show a construction of MDS matrices based on Companion matrices, which is very convenient for lightweight cryptography. 1
|
|
|
Classification of finite dimensional modules over string algebras
Macháč, Ondřej ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis we classify indecomposable finite dimensional modules over string alge- bras. In the introductory part we define string algebras and string modules and band modules. In the third chapter we prove the classification theorem and define functors used. In the fourth and fifth chapter we verify assumptions on the functors regarding string modules or band modules, respectively. In the last chapter we show that these functors are sufficient and we finish proofs of all the remaining assumptions of the main theorem. At last we show examples of classification. 1
|
|
|
Kan extensions and adjoint functors
Otrubů, Mavis ; Šaroch, Jan (advisor) ; Žemlička, Jan (referee)
This thesis is devoted to Kan extensions. First, we provide needed definitions and prove a theorem which gives us an existence condition for a Kan extensions. The proof of this theorem also contains a guide to constructing Kan extensions. The main goal is to present a result which puts Kan extensions and adjoint functors in relation. We also connect this theorem to global Kan extensions. We apply these abstract results in the last chapter, where we formulate and solve a particular problem concerning adjoint functors between the categories of G-sets. 1
|
|
|
AKS primality test and its variants
Ondo, Tomáš ; Žemlička, Jan (advisor) ; Pavlů, Jiří (referee)
In this thesis, the first polynomial deterministic primality test named AKS algori- thm is described. The thesis is focused on the time complexity of the algorithm. Several drawbacks which make this algorithm unsuitable for generating large prime numbers are described. Improvements derived from empirical data are summed up. These improve- ments are not proven, so they do not yield a deterministic test. The thesis continues with a comparison of the runtime of concrete implementations. The thesis also contains a variant of the AKS test, the Bernstein variant, which has a better time complexity. The execution of these algorithms is shown in examples. 1
|
|
|
Art gallery problem
Smolíková, Natálie ; Patáková, Zuzana (advisor) ; Žemlička, Jan (referee)
In this thesis, we study a classical problem in computational geometry, the Art Gallery Problem. The Art Gallery Problem originates from the question of what is the minimum number of guards required to see the entire gallery. The main goal of this paper is to provide proofs that ⌊n 3 ⌋ guards are sufficient for a simple polygon, and that ⌊n 4 ⌋ guards are sufficient for an orthogonal polygon. Our proof of the orthogonal version is a correction of Jorge Urrutia's proof. We also study the optimality of the results and the placement of guards. 1
|
guest ::
RSS feed.