| |
| |
|
Silné důkazové systémy
Mikle-Barát, Ondrej ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
R-OBDD is a new Cook-Reckhow propositional proof system based on combination of OBDD proof system and resolution proof system. R-OBDD has the strength of OBDD proof system - hard tautologies for resolution like PHPn or Tseitin contradictions have polynomially sized proofs in R-OBDD (R-OBDD p-simulates OBDD proof system as well as resolution). On the other hand, inference rules of R-OBDD are designed to be similar to inference rules of resolution, thus allowing to create a modified version of DPLL algorithm and possibly using heuristics used in various DPLL-like algorithms. This gives a possibility for a SAT solver more efficient than SAT solvers based on resolution proof system. We present design of a SAT solver, which is an adaptation of DPLL algorithm for the R-OBDD proof system. The algorithm is accompanied with proof of its correctness and we show that the run of the algorithm on an unsatisfiable formula can be transformed into tree-like refutation in the R-OBDD proof system.
|
| |
|
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,...
|
| |
|
Algorithms of the interpolation by multivariate polynomials
Doktorová, Alice ; Čermák, Libor (referee) ; Kureš, Miroslav (advisor)
This bachelor's work concerns to algorithms of the multivariate interpolation. The problem of the interpolation over the plane is studied in the first part of this work. In the next section, the multivariate Lagrange interpolation is described and the polynomial degree is discussed. A Mathematica program package was developed, by this, the multivariate interpolation over an arbitrary field can be solved.
|
|
Factorization of polynomials over finite fields
Straka, Milan ; Stanovský, David (referee) ; Žemlička, Jan (advisor)
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...
|
|
Some aspects of the discontinuous Galerkin method for the solution of convection-diffusion problems
Hájek, Jaroslav ; Najzar, Karel (referee) ; Feistauer, Miloslav (advisor)
This work is concerned with the numerical solution of initial-boundary value problems for convection-diffusion partial differential equations. Three methods are studied and compared for this purpose: the combined finite element - finite volume (FE-FV) method, the discontinuous Galerkin finite element (DGFE) method of lines, and the spacetime discontinuous Galerkin method. The combined FE-FV method uses piecewise linear conforming finite elements for the discretization of the diffusion terms and piecewise constant FV approximation of the convective terms. The relation between the FE and FV approximations is determined by the so-called lumping operator. In the DGFE method of lines, the space semidiscretization is carried out by piecewise polynomial functions constructed over a triangular mesh, in general discontinuous on interfaces between neighbouring elements. In the space-time DGFE method, the approximate solution is piecewise polynomial in space as well as in time. We discuss both theoretical and practical aspects of the methods, and present numerical results for each of them. For the DGFE method of lines we derive an a posteriori error estimate.
|
|
The design and cryptanalysis of the AES (Advanced Encyption Standard)
Říha, Jan ; Vábek, Jiří (referee) ; Tůma, Jiří (advisor)
Nazev prace: Konstrukce a kryptoanalyza AES (Advanced Encyption Standard) Autor: Jan Říha Katedra: Katedra Algebry Vedouci bakalafske prace: Doc. RNDr. Jin Tuma, DrSc. E-mail vedouciho bakalafske prace: Jiri.Tuma@mff.cuni.cz Abstrakt: V pfedlozene praci studujeme nejnovejsi symetrickou blokovou sifru AES. Nejprve se zabyvame vyvojem a vznikem sifry od vypsani souteze a2 po vyhlaseni vitezneho kandidata. Pote se venujeme jejf konstrukci, ve ktere se vyuziva nekterych netrivialnich poznatku algebry pfi praci s polynomy nad konecnym telesem. V teto kapitole je tez popsana prima inverzni sifra a ekvivalentni inverzni sifra slou^ici k desifrovani zasifrovanych dat. Ve tfeti kapitole zkoumame navrhovane implementace sifry AES na jednotlive platformy a nakonec rozebirame mozne utoky a odolnost Sifry AES vuci nim. Klicova slova: AES, sifra, implementace, kryptoanalyza Title: The design and cryptanalysis of the AES (Advanced Encyption Standard) Autor: Jan ftiha Department: Department of Algebra Supervisor: Doc. RNDr. Jin Tuma, DrSc. Supervisor's e-mail address: Jiri.Tuma@mff.cuni.cz Abstract: In the present work we study the newest symetric block cipher AES. At first we consider development and creation of the cipher from the start of selection proces till announcement of winning candidate. Then we turn to its...
|
guest ::
