|
|
Coloring knots
Nagy, Tomáš ; Stanovský, David (advisor) ; Šťovíček, Jan (referee)
The thesis deal with coloring knots by algebraical structures called quandles. We will introduce the theory that is necessary for understanding the knot coloring and we will prove that coloring is a knot invariant. The major part of the thesis is an experiment focused on coloring different knots by different classes of quandles. We will focus on knots which are hardly distinguished by other knot invariants, also the time complexity of coloring different classes of knots in dependency on the number of crossings and on the size of the quandle will be important for us. We will deal also with the connection between knot coloring and other knot invariants.
|
|
|
Algebraic inequalities over the real numbers
Raclavský, Marek ; Šťovíček, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis analyses the semialgebraic sets, that is, a finite union of solu- tions to a finite sequence of polynomial inequalities. We introduce a notion of cylindrical algebraic decomposition as a tool for the construction of a semialge- braic stratification and a triangulation of a semialgebraic set. On this basis, we prove several important and well-known results of real algebraic geometry, such as Hardt's semialgebraic triviality or Sard's theorem. Drawing on Morse theory, we finally give a proof of a Thom-Milnor bound for a sum of Betti numbers of a real algebraic set. 1
|
|
|
Algortihms for proving primality
Pavlů, Jiří ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
The goal of the thesis is introducing the reader to some of the algori- thms for proving primality along with practical usage of some of these algorithms. The main objective of the thesis is a presentation of Goldwasser-Killian primality test, which can be used to produce primality certificates, which can be verified very quickly. For better understanding of the test the thesis also includes an in- troduction to elliptic curves, which are the basis of the test. The thesis also shows how is a group of points on elliptic curves constructed and how to use this infor- mation for construction of algebraic formula for a sum of two points on a curve. Powered by TCPDF (www.tcpdf.org)
|
|
|
MQ problem
Středa, Adolf ; Žemlička, Jan (advisor) ; Šťovíček, Jan (referee)
The aim of this thesis is to describe a general MQ Problem with a focus on its variant called HFE, outline several attacks on a basic scheme based on HFE and describe a new attack on HFEz, a cryptosystem based on special polynomials over finite fields with a modification, which discards a portion of the output from the initial transformation. This ensures a dependency on more variables while keeping the same size of the field. The attack starts with a translation of HFE into HFE with branches, followed by a branch separating algorithm described in [Fel06]. The separation algorithm uses the public key to derive an operation, which induces (with addition) a non-associative algebra. Utilising some properties of non-associative algebras, a matrix, which can separate variables into distinct sets according to branches, is calculated. This leads to stripping off the HFEz modification and thus allowing us to attack directly the HFE polynomial. Powered by TCPDF (www.tcpdf.org)
|
|
|
Smart's algorithm
Sladovník, Tomáš ; Příhoda, Pavel (advisor) ; Šťovíček, Jan (referee)
The discrete logarithm problem is one of the most common trap- door functions in asymmetric cryptography and the use of elliptic curves over a finite field with prime characteristics seems to be a very efficient platform. This paper addresses the solution of a special type of elliptic curves where the number of points is equal to the characteristic of a field. Our goal is to construct a linear algorithm in goup operations and prove correctness. In order to create the algorithm, we will implement p-adic numbers, introduce the theory of formal groups and the formal logarithm and subgroups of an elliptic curve over the field of p-adic numbers. We will show that this type of curves is absolutely useless for cryptography because these curves are not safe. 1
|
|
|
Classes of modules arising in contemporary algebraic geometry
Slávik, Alexander ; Trlifaj, Jan (advisor) ; Šťovíček, Jan (referee)
In the setting of Noetherian or Dedekind domains, we investigate the properties of very flat and contraadjusted modules. These are the modules from the respective classes in the cotorsion pair (VF, CA) generated by the set of all modules of the form R[s−1 ]. Furthermore, we introduce the concept of locally very flat modules and pursue the analogy of their relation to very flat modules and the relation between projective and flat Mittag-Leffler modules. It is shown that for Noetherian domains, the class of all very flat modules is covering, if and only if the class of all locally very flat modules is precovering, if and only if the spectrum of the ring is finite; for domains of cardinality less than 2ω , this is further equivalent to the class of all contraadjusted modules being enveloping.
|
|
|
Elliptic curves and primality testing
Haníková, Adéla ; Drápal, Aleš (advisor) ; Šťovíček, Jan (referee)
The aim of the thesis is to desribe and implement the elliptic curve factorization method using curves in Edwards form. The thesis can be notionally divided into two parts. The first part deals with the theory of Edwards curves especially with properties of elliptic function fields. The second part deals with the factorization algorithm using Edwards form both formally and practically in the way the algorithm is really implemented. The contribution of this thesis is the enclosed implementation of the elliptic curve factorisation algorithm which can be run on a graphic card and which is faster than the state-of-the-art implementation GMP-ECM. Powered by TCPDF (www.tcpdf.org)
|
|
|
An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we describe an algorithm and implement a construction of a projective resolution and minimal projective resolution in the representation the- ory of finite-dimensional algebras. In this thesis finite-dimensional algebras are KQ /I where KQ is a path algebra and I is an admissible ideal. To implement the algorithm we use the package QPA [9] for GAP [2]. We use the theory of Gröbners basis of KQ-modules and the theory described in article Minimal Pro- jective Resolutions written by Green, Solberg a Zacharia [5]. First step is find a direct sum such that i∈Tn fn∗ i KQ = i∈Tn−1 fn−1 i KQ ∩ i∈Tn−2 fn−2 i I. Next important step to construct the minimal projective resolution is separate nontri- vial K-linear combinations in i∈Tn−1 fn−1 i I + i∈Tn fn i J from fn∗ i . The Modules of the minimal projective elements are i∈Tn (fn i KQ)/(fn i I). 1
|
|
|
Non-commutative Gröbner bases
Požárková, Zuzana ; Šťovíček, Jan (advisor) ; Stanovský, David (referee)
In the presented work we define non-commutative Gröbner bases including the necessary basis of non- commutative algebra theory and notion admissible ordering. We present non-commutative variant of the Buchberger algorithm and study how the algorithm can be improved. Analogous to the Gebauer-Möller criteria lead us to detect almost all unnecessary obstructions in the non-commutative case. The obstructions are graphically ilustrated. The Buchberger algorithm can be improved within redundant polynomials. This work is a summary and its specification of the results of some known authors engaged in this field. Presented definitions are ilustrated on examples. We perform proves of some of the statements which have been proven differently by other authors. Powered by TCPDF (www.tcpdf.org)
|
|
|
Weil pairing
Luňáčková, Radka ; Drápal, Aleš (advisor) ; Šťovíček, Jan (referee)
This work introduces fundamental and alternative definition of Weil pairing and proves their equivalence. The alternative definition is more advantageous for the purpose of computing. We assume basic knowledge of elliptic curves in the affine sense. We explain the K-rational maps and its generalization at the point at infinity, rational map. The proof of equivalence of the two mentioned definitions is based upon the Generalized Weil Reciprocity, which uses a concept of local symbol. The text follows two articles from year 1988 and 1990 written by L. Charlap, D. Robbins a R. Coley, and corrects a certain imprecision in their presentation of the alternative definition. Powered by TCPDF (www.tcpdf.org)
|
guest ::
