|
|
Algorithms for Minkowski sums of polygons
Šimek, Daniel ; Patáková, Zuzana (advisor) ; Příhoda, Pavel (referee)
This bachelor's thesis deals with the Minkowski sum of two non-convex polygons in the plane. Specifically, it focuses on describing and comparing two methods for computing the Minkowski sum: the decomposition method and the convolution method. This thesis provides a detailed presentation of both methods, including necessary definitions and illustrative images. In the final chapter, both methods are compared using the CGAL C++ library on various inputs. 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
|
|
|
Continued fractions in local fields
Červenková, Eliška ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
The theses concerns the topic of p-adic Ruban and Browkin continued frations and their properties. To begin with, the concept of p-adic numbers is introduced and the necessary theory is shown. Next, continued fractions are defined and their convergence in both real and p-adic numbers is analyzed. Following this, the theses examines Ruban continued fractions and presents an algorithm for determining whether the expansion is terminating, along with a derivation of the maximum number of algorithmic steps required. It also holds that if Ruban expansion is not terminating, then it is periodic. A detailed description of the periodicity, including its properties, is provided. Then the focus is shifted to Browkin continued fractions. It holds that every rational number has a finite Browkin continued fraction. This claim is subsequently proven. The theses concludes with examples that demonstrate the properties of both Ruban and Browkin continued fractions. 1
|
|
|
The Tate-Shafarevich group of an elliptic curve
Zvěřina, Adam ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis deals with the Tate-Shafarevich group and its relation to rational points on the curve and its rank. We first define the notion of profinite groups and characterize them as Galois groups of field extensions. Then we define the Tate-Shafarevich group using Galois cohomology and explain its relation to the rational points on the curve. Finally, we formulate the Birch-Swinnerton-Dyer conjecture, which relates the rank of an elliptic curve and the order of its Tate-Shafarevich group. 1
|
|
|
Sieving in factoring algorithms
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. Apart from several well-known variants, we present our own proposals of both quadratic and number field sieve and analyze their advantages and disadvantages in detail. 1
|
|
|
Application of invertible elements in a zero-knowledge proof
Kučerová, Karolína ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This work is focused on the description of one verifiable encryption scheme, specifically a zero-knowledge proof of knowledge protocol. Verifiable encryption allows us to prove properties of data without revealing its content. The main goal of the presented method is verification of knowledge of a secret key. This method can be used for group signa- tures, multiple steps secret sharing, key escrow protocols, and many others cryptographic protocols. It is based on the hardness of the Ring-LWE problem and problems of finding solutions to linear relations over some ring. It uses the principle of rejection sampling. The method is build on two closely described cryptographic protocols, Ring-LWE and Fiat-Shamir with aborts. It uses the construction of polynomial rings R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1
|
|
|
Local properties of modules
Lysoněk, Tomáš ; Hrbek, Michal (advisor) ; Příhoda, Pavel (referee)
This thesis introduces module properties of projectivity and flatness relative to classes of finitely presented modules, these being generalization of projectivity and pure pro- jectivity. Then it gives proof of ascent and descent of these properties through non- commutative ring homomorphisms with certain properties, most importantly reflection of pure epimorphisms. For relative case ascent and descent through flat ring homomor- phisms, which reflect pure epimorphisms, is given. Finally, these results are applied in the setting of homomorphisms arising as central extensions of pure and faithfully flat central ring homomorphisms. 1
|
|
|
Structural and categorical description of classes of abelian groups
Dvořák, Josef ; Žemlička, Jan (advisor) ; Modoi, George Ciprian (referee) ; Příhoda, Pavel (referee)
The work presents results concerning the self-smallness and relative smallness properties of products in the category of abelian groups and in Ab5-categories. Criteria of relative smallness of abelian groups and a characterization of self-small products of finitely generated abelian groups are also given. A decomposition theory of UD-categories and in consequence a unified theory of decomposition in categories of S-acts is developed with applications on (auto)compactness proper- ties of S-acts. A structural description of compact objects in two categories of S-acts is provided. The existence of projective covers in categories S − Act and S − Act0 and the issue of perfectness of a monoid with zero are discussed. 1
|
|
|
Groebner bases
Mašková, Kristýna ; Trlifaj, Jan (advisor) ; Příhoda, Pavel (referee)
Gröbner basis is a particular kind of a generating set of an ideal in the polynomial ring S = K[x1, . . . , xn]. This notion is based upon the concept of a monomial order. We define these concepts and present Buchberger's criterion, that enables us to effectively verify whether a generating set is a Gröbner basis. We introduce Buchberger's algorithm, that produces a Gröbner basis from a finite set of generators. We consider a special case of linear homogeneous ideals, where Gröbner basis can be computed simply by the Gaussian elimination. Finally, we extend this theory to submodules of free modules and briefly indicate how to use Gröbner bases to prove Hilbert's syzygy theorem. 1
|
|
|
Verifiable Delay Functions z Lucasových posloupností
Krňák, Tomáš ; Hubáček, Pavel (advisor) ; Příhoda, Pavel (referee)
Lucas sequences are constant-recursive integer sequences with a long history of appli- cations in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus. First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Second, we demonstrate the feasibility of constructing practically efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our con- struction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connec- tion between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field. 1
|
guest ::
