|
|
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 e-mail 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
|
|
| |
|
| |
|
|
Combinatorial group theory and cryptography
Ferov, Michal ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.
|
|
|
Constructions of Commutative Semirings and Radical Rings
Korbelář, Miroslav ; Kepka, Tomáš (advisor) ; Němec, Petr (referee) ; Příhoda, Pavel (referee)
In this dissertation we deal with constructive methods applied to the commutative semirings and commutative radical rings. In Chapter 2 we study the class S of the commutative subdirectly irreducible radical rings. We present a few constructive methods for them and using the reflection of the category of the commutative rings into the category of the commutative radical rings we derive a lot of examples of rings in S with various properties. We prove that a ring S 2 S is noetherian if and only if it is finite. We show partial results in the classification of factors of S modulo monoliths. In Chapter 3 we introduce, using the p-prime valuation for all primes p, a set of characteristic sequences that can be assign to every subsemiring of Q+. We find and classify all maximal subsemirings of positive rational numbers and show that every proper subsemiring of Q+ is contained in at least one of them. This results was published in [16]. In Chapter 4 we construct, using the approach from the Chapter 4, a new large subclass of the class CongSimp of all proper congruence-simple subsemirings of Q+, classify all the maximal elements of CongSimp and show that every element of CongSimp is contained in at least one of them. In Chapter 5 we find an equivalent condition under which is the semiring Q+[ ] C, 2 C, contained in...
|
|
|
Singular points of algebraic varieties
Vančura, Jiří ; Příhoda, Pavel (advisor) ; Šťovíček, Jan (referee)
This thesis is an introduction to exploring singularities of algebraic varieties. In the first chapter, we state basic definitions and theorems necessary for exploring singularities. Firstly, we define algebraic varieties and their corresponding ideals and explain the term of Krull dimension. We also focus on the local properties of varieties. In the second chapter, we begin by examining the term of singularity in detail and introducing methods for searching for singularities. We prove two theorems about the shape and the dimension of singularities. In the second part, we prove theorems about the zero divisors, which enable us to define Cohen-Macaulay and Gorenstein rings. We use them to roughly classify singularities of algebraic varieties.
|
|
| |
|
|
Algebraic proofs of Dirichlet's theorem on arithmetic progressions
Čech, Martin ; Kala, Vítězslav (advisor) ; Příhoda, Pavel (referee)
Dirichlet's theorem on arithmetic progressions says that there are infinitely many primes in any arithmetic progression an = kn + with coprime k, . The original proof of this theorem was analytic using a lot of non-elementary methods. The goal of this thesis is to give sufficient and necessary conditions on k and under which a more elementary algebraic proof of the theorem can exist, and give the proof in these cases. 1
|
guest ::
