|
Congruent numbers, elliptic curves, and L-functions
Kotyk, Jan ; Kala, Vítězslav (advisor) ; Příhoda, Pavel (referee)
The main goal of this thesis is to connect the ideas surrounding the congruent number problem. At first we define congruent numbers and elliptic curves which naturally emerge from this problem. We then define the addition law on points lying on such curves and show that it actually defines an abelian group structure on the set of those points. We then focus on the study of elliptic curves and their groups over finite fields to give us new insight on the congruent number problem. With this we then later define Zeta-functions and L-functions. At the end we see a connection between the property of being a congruent number and the rank of the corresponding elliptic curve which is then used to classify first few congruent and non-congruent numbers. 1
|
|
Coconnected algebras
Vlasák, Lukáš ; Barto, Libor (advisor) ; Příhoda, Pavel (referee)
If every homomorphism from the n-th power of an algebra A to A depends on one variable only, then we say that A is n-coconnected. For every integer n ≥ 2 there exists a n-coconnected algebra, which is not (n + 1)-coconnected. Examples of these algebras constructed in previous articles were large in terms of either cardinality of the algebra or the number of operations. The goal of this thesis is to improve the lower and upper estimate of the lowest possible cardinality of a n-coconnected and not (n + 1)- coconnected algebra. There is already a construction of these algebras for every possible n with cardinality 2n and for n ≥ 3 the lower estimate of the lowest possible cardinality is currently n + 1. In this thesis we will construct examples of the smallest possible n-coconnected and not (n + 1)-coconnected algebras for every n ≥ 2. 1
|
|
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
|