|
|
Barvení uzlů
Nagy, Tomáš ; Stanovský, David (vedoucí práce) ; Šťovíček, Jan (oponent)
V práci se zabýváme barvením uzlů pomocí algebraických struktur zvaných quandly. Představíme teorii potřebnou pro porozumění barvení a dokážeme, že barvení je skutečně invariantem uzlů. Stěžejní část práce tvoří experiment zaměřený na obarvování různých tříd uzlů různými quandly. Experiment je zaměřen především na zkoumání uzlů, které jsou obtížně odlišitelné jinými invarianty a také na zkoumání časové složitosti barvení jednotlivých tříd uzlů v závislosti na počtu křížení barveného uzlu a na velikosti barvícího quandlu. Zkoumáme také souvislost barvení jednotlivými třídami quandlů s jinými invarianty uzlů.
|
|
|
Algebraické nerovnice nad reálnými čísly
Raclavský, Marek ; Šťovíček, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato práce zkoumá semialgebraické množiny, tedy množiny definované jako konečná sjednocení řešení konečné soustavy polynomiálních nerovnic. Předsta- víme koncept válcového rozkladu, který využijeme jako nástroj pro sestrojení stratifikačního rozkladu a triangulace semialgebraické množiny. Na tomto základě dokážeme několik důležitých a známých výsledků reálné algebraické geometrie, jako je Hardtova věta o semialgebraické trivialitě nebo Sardova věta. S využitím Morseho teorie nakonec dokážeme Thom-Milnorovu nerovnost na součet Bettiho čísel reálné algebraické množiny. 1
|
|
|
Algoritmy dokazující prvočíselnost
Pavlů, Jiří ; Šťovíček, Jan (vedoucí práce) ; Žemlička, Jan (oponent)
Cílem práce je seznámit čtenáře s různými algoritmy pro dokazování prvočíselnosti spolu s použitím některých těchto algoritmů v praxi. Práce je za- měřena na Goldwasser-Killianův test, jehož výstupem je certifikát, který je možné rychle ověřit. Aby bylo možné tomuto testu porozumět, obsahuje práce úvod do teorie eliptických křivek, na nichž je test založen. Práce také ukazuje, proč tvoří sčítání na eliptické křivce grupu, jak se tato grupa konstruuje a jak těchto znalostí využít pro tvorbu algebraického vzorce pro výpočet součtu dvou bodů. Powered by TCPDF (www.tcpdf.org)
|
|
|
MQ problém
Středa, Adolf ; Žemlička, Jan (vedoucí práce) ; Šťovíček, Jan (oponent)
Cílem této bakalářské práce je popsat obecný MQ problém, především jeho variantu zvanou HFE, nastínit některé útoky na základní schéma založené na HFE a následně popsat nový útok na HFEz, systém vzniklý modifikací HFE, kdy se část výstupů z úvodní transformace opomene. Modifikace HFEz zajistí závislost vstupu do HFE polynomu na větším množství proměnných při zachování velikosti rozšíření tělesa. Útok na tuto modifikaci spočívá v překladu HFEz na HFE s větvením a následné aplikaci algoritmu pro separaci jednotlivých větví navrženého v [Fel06]. Separační algoritmus přes veřejný klíč vytvoří operaci, která společně se sčítáním tvoří komutativní, neasociativní algebru. Následně se aplikací několika poznatků o neasociativních algebrách za pomoci této operace spočte matice, která umožní separovat proměnné do několika sad odpovídajících jednotlivým větvím. Díky tomuto převodu můžeme následně provést útok přímo na HFE polynom neovlivněného modifikací HFEz. Powered by TCPDF (www.tcpdf.org)
|
|
|
Smartův algoritmus
Sladovník, Tomáš ; Příhoda, Pavel (vedoucí práce) ; Šťovíček, Jan (oponent)
Problém diskrétního logaritmu je jedním z pilířů asymetrické kryp- tografie a jeho použití na eliptických křivkách nad konečným prvočíselným tělesem se jeví jako velice efektivní. Tato práce se zabývá jeho řešením na eliptických křivkách, jejichž velikost je rovna velikosti onoho tělesa. Cílem této práce je se- stavit funkční algoritmus, který bude schopen řešit tento problém v lineárním čase podle počtu grupových operací a ověřit jeho správnost. K vytvoření algo- ritmu je potřeba pracovat s p-adickými čísly, zavést základy teorie formálních grup, formálního logaritmu a zavést podgrupy eliptických křivek nad p-adickými čísly. Ukáže se, že použití tohoto typu křivek je pro kryptografické účely naprosto nevhodné, a že tyto křivky nejsou bezpečné. 1
|
|
|
Classes of modules arising in contemporary algebraic geometry
Slávik, Alexander ; Trlifaj, Jan (vedoucí práce) ; Šťovíček, Jan (oponent)
V kategorii modulů nad noetherovskými nebo Dedekindovými obory zkoumáme vlastnosti velmi plochých a kontraadjustovaných modulů, tj. modulů z odpovídajících tříd v kotorzním páru (VF, CA) generovaném množinou všech modulů tvaru R[s−1 ]. Dále definujeme lokálně velmi ploché moduly a vyšetřujeme jejich vztah k velmi plochým modulům jako analogii vztahu projektivních a plo- chých Mittag-Lefflerových modulů. Pro noetherovské obory ukazujeme, že třída všech velmi plochých modulů je pokrývající, právě když třída všech lokálně velmi plochých modulů je předpokrývající, právě když spektrum příslušného okruhu je konečné. Pro obory mohutnosti menší než 2ω je toto dále ekvivalentní výroku, že třída všech kontraadjustovaných modulů je pokrývající.
|
|
|
Elliptické křivky a testování prvočíselnosti
Haníková, Adéla ; Drápal, Aleš (vedoucí práce) ; Šťovíček, Jan (oponent)
Cílem této práce je popsat a implementovat metodu faktorizace pomocí eliptických křivek s~využitím křivek v~Edwardsově tvaru. Práce se dá pomyslně rozdělit na dvě části, přičemž první část práce se zabývá teorií Edwardsových křivek, zejména vlastnostmi příslušných eliptických funkčních těles. Druhá část pak popisuje využití ve faktorizačním algoritmu a to čistě teoreticky i~prakticky tak, jak je algoritmus skutečně implementován. Přínosem této práce je přiložená implementace faktorizace pomocí eliptických křivek využívající grafickou kartu, která je díky paralelizaci rychlejší než obecně nejpoužívanější implementace GMP-ECM. Powered by TCPDF (www.tcpdf.org)
|
|
|
An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
V této práci popisujeme algoritmus na hledání projektivní resolventy a mi- nimální projektivní resolventy v teorie reprezentací konečně-dimenzionálních al- geber. V našem případě konečně-dimenzionální algebrou je KQ /I, kde KQ je algebra cest a I je přípustný ideál. Práce obsahuje implementaci minimalní pro- jektivní resolventy v balíku QPA. Používáme teorii Gröbnerových bazí pro KQ- moduly a článek Minimal Projective Resolutions autorů Green, Solberg a Zacha- ria [5]. Prvním krokem je vyjádření ⊕i∈Tn fn∗ i KQ = ⊕i∈Tn−1 fn−1 i KQ ∩ ⊕i∈Tn−2 fn−2 i I. Druhým krokem pro nalezení minimalní projektivní resolventy je z mno- žiny prvků fn∗ i odebrat všecky netriviálni K-lineární kombinace, které leží v ⊕i∈Tn−1 fn−1 i I + ⊕i∈Tn fn∗ i J. Výsledné moduly minimální projektivní resol- venty jsou ⊕i∈Tn fn i KQ / ⊕i∈Tn fn i I. 1
|
|
|
Nekomutativní Gröbnerovy báze
Požárková, Zuzana ; Šťovíček, Jan (vedoucí práce) ; Stanovský, David (oponent)
V předložené práci definujeme nekomutativní Gröbnerovy báze, včetně potřebných základů nekomutativní algebry a pojmu přípustné uspořádání. Je zde představena nekomutativní varianta Buchbergerova algoritmu a podrobně studována vylepšení vedoucí k efektivnímu výpočtu. Studium netriviálních obstrukcí nás přivádí k analogii Gebauer-Möller kritérií vedoucích k odstranění většině nadbytečných obstrukcí v nekomutativním případě. Uvádíme zde grafickou interpretaci obstrukcí. Vylepšení algoritmu lze také dosáhnout pomocí redundantních polynomů. Tato práce je shrnutím a zpřesněním výsledků některých známých autorů zabývajících se touto problematikou. V práci definované pojmy jsou ilustrovány na příkladech. Předkládáme zde důkazy některých tvrzení, která byla odlišným způsobem dokázána jinými autory. Powered by TCPDF (www.tcpdf.org)
|
|
|
Weilovo párování
Luňáčková, Radka ; Drápal, Aleš (vedoucí práce) ; Šťovíček, Jan (oponent)
Práce popisuje základní a alternativní definici Weilova párování a dokazuje jejich ekvivalenci. Výhodou alternativní definice je vhodnější tvar pro výpočty. Předpokládá se znalost základů teorie eliptických křivek v afinním smyslu. Je popsán pojem K-racionálního zobrazení a následně jeho dodefinování v nevlastním bodě, racionální zobrazení. Důkaz ekvivalence oněch dvou definic Weilova párování se opírá o Zobecněnou Weilovu reciprocitu, která je formulována pomocí lokálního symbolu a je jí věnována samostatná kapitola. Text vychází z dvou článků o eliptických křivkách z roků 1988 a 1990 od L. Charlapa, D. Robbinse a R. Coleyho, přičemž je odstraněna nepřesnost, které se při formulaci alternativní definice dopustili. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.