|
|
Multivariační kryptografie
Jančaříková, Irena ; Žemlička, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
Tato práce se zabývá multivariační kryptografii. Konkrétně obsahuje popis MQ problému a důkaz jeho NP-úplnosti. V části o MQ problému je i popis obecného schématu pro tvorbu veřejné části asymetrických kryptosystémů založeným na MQ problému. V této části také práce popisuje QMLE problém, který je důležitý pro tvar soukromého klíče kryptosystémů založených na MQ problému. Práce dále obsahuje popis vlivu struktury zobrazení, které se objevují v QMLE problému, na časovou složitost řešení QMLE problému. Vliv na časovou složitost byl zjištěn pomocí experimentálního měření na naprogramovaném algoritmu. Na konci práce je uveden popis vybraných multivariačních kryptosystémů založeným na MQ problému. U popsaných kryptosystémů je detailní popis šifrování a dešifrování pomocí vybraných kryptosystémů a časové odhady těchto operací. Práce také obsahuje odhady na paměťové nároky na uložení soukromého a veřejného klíče popsaných kryptosystémů. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
| |
|
| |
|
|
Problém realizace von Neumannovsky regulárních okruhů
Mokriš, Samuel ; Růžička, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Název práce: Problém realizace von Neumannovsky regulárních okruhů Autor: Samuel Mokriš Katedra: Katedra algebry Vedoucí diplomové práce: Mgr. Pavel Růžička, Ph.D., Katedra algebry Abstrakt: Každému okruhu R s jednotkou lze přiřadit komutativní monoid V (R) tříd izomor- fismů konečně generovaných pravých projektivních R-modulů. Příslušný monoid je redukovaný s jednotkou, v případě von neumannovsky regulárních okruhů má navíc Rieszovu zjemňovací vlastnost. Práce se zabývá otázkou, za jakých podmínek je naopak redukovaný komuta- tivní zjemňovací monoid s jednotkou realizovatelný jako V (R) nějakého von neumannovsky regulárního okruhu či dokonce regulární algebry, zejména pro spočetné monoidy. Jsou uve- dena dvě možná zobecnění konstrukce V (R) pro okruhy bez jednotky a je rozebrán vztah mezi nimi. Za tímto účelem jsou rozvíjeny vlastnosti okruhů s lokálními jednotkami a modulů nad takovými okruhy. Dále je v práci předvedena konstrukce leavittovských algeber cest nad ori- entovanými grafy s násobnými hranami a kontrukce monoidu asociovaného s grafem, který je izomorfní monoidu V (R) leavittovské algebry cest nad týmž grafem. Tyto metody jsou využity k předvedení, jak realizovat direktní sjednocení konečně...
|
|
|
Gröbnerovy báze
Petržilková, Lenka ; Žemlička, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
V této práci si nejprve připomeneme základní Buchbergerův algoritmus pro výpočet Gröbnerovy báze nad komutativními polynomiálními okruhy. Zabýváme se také jednoznačností Gröbnerovy báze pro daný ideál. Dále zkoumáme méně známý, ale pro některé případy efektivnější Faugèreův F4 algoritmus. V závěru první kapitoly tyto dva algoritmy porovnáme. V druhé kapitole rozebereme zobecnění Buchbergerova algoritmu pro nekomutativní okruhy a to jak pro volné tak pro faktorové algebry. Na rozdíl od komu- tativního případu zde mohou mít i konečně generované ideály nekonečné Gröbnerovy báze. Mimo jiné zde zkoumáme tzv. kvazi-nuly, tj. prvky, ze kte- rých přenásobením libovolným termem vznikne nula, a jejich roli při redukci polynomu množinou. 1
|
|
| |
|
| |
|
| |
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
host ::
RSS.