|
|
Qudratic field based cryptography
Straka, Milan ; Stanovský, David (advisor) ; Žemlička, Jan (referee)
Imaginary quadratic fields were first suggested as a setting for public-key cryptography by Buchmann and Williams already in 1988 and more cryptographic schemes followed. Although the resulting protocols are currently not as efficient as those based on elliptic curves, they are comparable to schemes based on RSA and, moreover, their security is believed to be independent of other widely-used protocols including RSA, DSA and elliptic curve cryptography. This work gathers present results in the field of quadratic cryptography. It recapitulates the algebraic theory needed to work with the class group of imaginary quadratic fields. Then it investigates algorithms of class group operations, both asymptotically and practically effective. It also analyses feasible cryptographic schemes and attacks upon them. A library implementing described cryptographic schemes is a part of this work.
|
|
| |
|
|
Forest in life of medieval people on example of royal forest by Křivoklát
Trachtová, Nela ; Žemlička, Josef (advisor) ; Musílek, Martin (referee)
Wood was very important in life of medieval people. But its importance was changing in relation to social status of the person, who use the wood. King was hunting in forests, and it was a sovereigns, who began with hunting in the area of Křivoklát wood. The sovereigns founded many castles there, for example Křivoklát, Nižbor and Týřov, and the most important function of this castles that they where places, where it was possible to hunt. Sovereign was owner of this area, and he didn't want to give villages and other goods there. So we know, that the villages, which were given monasteries by princes and kings, were situated on the border of Křivokláts wood. We know gentry from Křivoklát too. There were some men, who were witness on the records of sovereign. We can name Zdeslav of Čistá, Vlček, Vacemil and Henry of Zvíkovec or Kuno of Kounov. By castle Křivoklát arose a system of royal man, which was founded by the king Přemysl Otakar II. There were two groups, the first were noble men and the second were low-born. Their duties were connected above all with defence of castle, but they had other duties too. Kings founded some cities too. In relation to area of Křivoklát played the biggest importance town Beroun and Rakovník. Beroun was a royal town, and inhabitans of Beroun could use woodland pasturage in...
|
|
| |
|
|
Solving systems of equations over commutative rings
Seidl, Jan ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
The object of this work is to offer algorithm how can be solved systems of linear equations Ax=b over principal ideal rings. We prove that for every nonzero matrix over principal ideal rings there exists its Smith form. Using Smith form we transform the system of equations to simple diagonal form and we show how we can obtain the solution of the original system from its diagonal form. Whole procedure we demonstrate by the examples over Z, Zm and Q[x]. Thereafter we show how is possible to implement the algorithm for these rings by using software Mathematica. The work should provide procedure according to which shold not be difficult to modify algorithm to gain solution over another rings. 1
|
|
|
Algorithm for word morphisms fixed points
Matocha, Vojtěch ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
In the present work we study the first polynomial algorithm, which tests if the given word is a fixed point of a nontrivial morphism. This work contains an improved worst-case complexity estimate O(m · n) where n denotes the word length and m denotes the size of the alphabet. In the second part of this work we study the union-find problem, which is the crucial part of the described algorithm, and the Ackermann function, which is closely linked to the union-find complexity. We summarize several common methods and their time complexity proofs. We also present a solution for a special case of the union-find problem which appears in the studied algorithm. The rest of the work focuses on a Java implementation, whose time tests correspond to improved upper bound, and a visualization useful for particular entries.
|
|
|
Varieties of superalgebras
Lišková, Adéla ; Žemlička, Jan (advisor) ; Barto, Libor (referee)
The goal of the thesis is to introduce the basics of the theory of superalgebras, that is Z2-graded algebras over a field of characteristic different from two, as well as to present necessary basics of universal and multilinear algebra, especially the tensor product and the terms variety of algebra and ideal of identities. We present the definitions of algebra and superalgebra including examples, we then look into the tensor product of superalgebras and its properties, Clifford and Grassmann superalgebras. A part of the thesis is dedicated to the construction of the free nonassociative algebra and the clarification of the relationship between varieties of algebras and ideals of identities including the specification of said relationship for superalgebras. The thesis also deals with varieties of superalgebras. 1
|
|
| |
|
|
Applications of Gröbner bases in cryptography
Fuchs, Aleš ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
Title: Applications of Gröbner bases in cryptography Author: Aleš Fuchs Department: Department of Algebra Supervisor: Mgr. Jan Št'ovíček Ph.D., Department of Algebra Abstract: In the present paper we study admissible orders and techniques of multivariate polynomial division in the setting of polynomial rings over finite fields. The Gröbner bases of some ideal play a key role here, as they allow to solve the ideal membership problem thanks to their properties. We also explore features of so called reduced Gröbner bases, which are unique for a particular ideal and in some way also minimal. Further we will discuss the main facts about Gröbner bases also in the setting of free algebras over finite fields, where the variables are non-commuting. Contrary to the first case, Gröbner bases can be infinite here, even for some finitely generated two- sided ideals. In the last chapter we introduce an asymmetric cryptosystem Polly Cracker, based on the ideal membership problem in both commutative and noncommutative theory. We analyze some known cryptanalytic methods applied to these systems and in several cases also precautions dealing with them. Finally we summarize these precautions and introduce a blueprint of Polly Cracker reliable construction. Keywords: noncommutative Gröbner bases, Polly Cracker, security,...
|
|
|
Factorization of polynomials over finite fields
Straka, Milan ; Žemlička, Jan (advisor) ; Stanovský, David (referee)
Nazcv prace: Faktorizace polynoinu nad konccnynii telesy Autor: Milan Straka Katcdra (ustav): Katcdra algebry Vedouci bakalarske prace: Mgr. Jan Zcmlicka, Ph.D. E-mail vedouciho: Jan.Zemlicka((hnff. cuni.cz Abstrakt: Cilem prace je prozkoumat problem rozkladu polynomn nad konecnym telc- scm na soucin ircducibilnich polynoinu. PopHanim nekolika algoritmu hledaji- cich tento rozklad se ukaze, ze tento problem je vzdy fcsitclny v polynornialnim case vzhleclem kc stupni polynomu a poctu prvku konecneho telcsa. U jeduoho z algoritnm je po])sana implenientace s vclnii clobrou asymptotic- kou casovou slozito.sti O(nLylD log c/}, kdc i\. jc stupen rozkladaneho polynuinn nad telesem « q prvky. Program pouzivajiei jcdnodnssi, ale prakticky rychlcjsi variantu tohoto algoritnm jc soucasti ])racc. Klicova slova: faktorizace, kouecna telesa, polynoniy, algoritmns Title: Factoring polynomials over finite fields Author: Milan Straka Department: Department of Algebra Supervisor: Mgr. Jan Zemlicka, Ph.D. Supervisor's e-mail address: Jan. Zcirilicka@mJJ.cum.cz Abstract: The goal of this work is to present the problem of the decomposition of a polyno- mial over a finite field into a product of irreducible polynomials. By describing algorithms solving this problem, we show that the decomposition can always be found in...
|
guest ::
RSS feed.