
The TateShafarevich group of an elliptic curve
Zvěřina, Adam ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis deals with the TateShafarevich 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 TateShafarevich group using Galois cohomology and explain its relation to the rational points on the curve. Finally, we formulate the BirchSwinnertonDyer conjecture, which relates the rank of an elliptic curve and the order of its TateShafarevich 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 wellknown 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 zeroknowledge 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 zeroknowledge 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 RingLWE 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, RingLWE and FiatShamir 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 selfsmallness and relative smallness properties of products in the category of abelian groups and in Ab5categories. Criteria of relative smallness of abelian groups and a characterization of selfsmall products of finitely generated abelian groups are also given. A decomposition theory of UDcategories and in consequence a unified theory of decomposition in categories of Sacts is developed with applications on (auto)compactness proper ties of Sacts. A structural description of compact objects in two categories of Sacts 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 constantrecursive 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 timelock 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


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. In addition, we present our own variant of the quadratic sieve, which has relatively large advantages in some areas compared to other known suggestions. 1


Modules over Gorenstein rings
Pospíšil, David ; Trlifaj, Jan (advisor) ; Příhoda, Pavel (referee) ; Herbera Espinal, Dolors (referee)
Title: Modules over Gorenstein rings Author: David Pospíšil Department: Department of Algebra Supervisor: Prof. RNDr. Jan Trlifaj, DSc. Supervisor's email address: trlifaj@karlin.mff.cuni.cz Abstract: The dissertation collects my actual contributions to the clas sification of (co)tilting modules and classes over Gorenstein rings. Com pared with the original intent we get a more general result in classification of (co)tilting classes namely for general commutative noetherian rings (see the third paper in this dissertation). The dissertation consists of an introduction and three papers with coauthors. The first paper (published in Contemp. Math.) contains a classification of all (co)tilting modules and classes over 1 Gorenstein commutative rings. The second paper (published in J. Algebra) contains a classification of all tilting classes over regular rings of Krull dimen sion 2 and also a classification of all tilting modules in the local case. Finally the third paper (preprint) contains a classification of all (co)tilting classes and also torsion pairs over general commutative noetherian rings. All these classi fications are in terms of subsets of the spectrum of the ring and by associated prime ideals of modules. Keywords: (co)tilting module, (co)tilting class, torsion pair, Gorenstein ring, regular ring,...


Analysis of the stream cipher QUAD
Čurilla, Marcel ; Holub, Štěpán (advisor) ; Příhoda, Pavel (referee)
Title: Analysis of the stream cipher QUAD Author: Marcel Čurilla Department: Katedra algebry Supervisor: doc. Mgr. Štěpán Holub, Ph.D. Abstract: Stream cipher QUAD was introduced in 2006 on Eurocrypt by Côme Ber bain, Henri Gilbert a Jacques Patarin cite quad. The authors showed a reduction of this cipher for the problem of solving m quadratic equations of n variables over finite fields known as the MQ problem. For simplicity, they considered only the case of the field GF(2). In this thesis I introduce this stream cipher. I show the proof (reduction) of safety ciphers QUAD for MQ problem over any finite field GF(q). I describe the basic met hods for the solution of system of quadratic equations over finite fields, linearization and relinearization. I focus on XL algorithm  which is currently the fastest algo rithm for solving quadratic systems. This algorithm was designed precisely to deal with overdefined quadratic systems. While analyzing the cipher QUAD I show for what instance is a cipher QUAD breakable and vice versa for what instance is the security guaranteed. Keywords: stream cipher, QUAD, MQ problem, algorithm XL, 1
