|
|
Aplikace Groebnerových bází
Skalová, Marie ; Příhoda, Pavel (vedoucí práce) ; Šťovíček, Jan (oponent)
Groebnerovy báze lze využít jako nástroj algebraické geometrie s aplikací v dokazo- vání geometrických tvrzení. V této práci představujeme metodu automatického dokazo- vání geometrických tvrzení ve dvou variantách, nejprve podle učebnice D. Cox, J. Little, D. O'Shea Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra, následně podle učebnice D. Stanovský, L. Barto, Počítačová algebra. Nejprve zde shrneme potřebnou teorii k odvození metody automa- tického dokazování. Dále teorii potřebnou k definici Groebnerovy báze a k vyslovení vět popisující její základní vlastnosti. Součástí práce jsou řešené příklady, na kterých jednot- livé kroky metody motivujeme, a také řešené příklady z již zmíněné učebnice autorů D. Cox, J. Little, D. O'Shea, některé z nich oběma variantami. V druhé kapitole se nachází vlastní důkaz rozkladu konkrétní algebraické množiny. 1
|
|
|
Malé kořeny celočíselných polynomů více proměnných
Todorovová, Dora ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Tato práce se zabývá Coppersmithovou metodou na hledání kořenů celo- číselných polynomů modulo N, která je založena na redukci báze mřížky. Nejprve zadefinujeme pojem mřížka a ukážeme si LLL algoritmus ve zjed- nodušené podobě. Dále popíšeme Coppersmithovu metodu a tvrzení, která se k ní vztahují. Následně ukážeme řešený příklad z článku od D. Boneh a G. Durfee a obecný postup z článku od E. Jochemsz a A. May, který do- plníme o několik důkazů navíc. V poslední kapitole vyřešíme příklady pomocí obecného postupu. 1
|
|
|
Compact modules over nonsingular rings
Kálnai, Peter ; Žemlička, Jan (vedoucí práce) ; Breaz, Simion (oponent) ; Příhoda, Pavel (oponent)
Tato disertace obsahuje několik nových výsledků, ve kterých využíváme vnitřní strukturu nesingulárních, speciálně samoinjektivních von Neuman- novsky regulárních okruhů. Nejdříve popíšeme kategoriální a množinově- teoretické podmínky, za kterých jsou všechny součiny kompaktních objektů kompaktními, přičemž pojem kompaktnosti je tady vztažen s ohledem na pevnou podtřídu objektů. Speciálními případy, kdy taková uzávěrová vlast- nost platí, jsou klasické modulové kategorie nad okruhy našeho zaměření. Navíc ukážeme, že případný protipříklad pro Köetheho hypotézu by mohl mít tvar spočetného lokálního podokruhu vhodného jednoduchého, samoin- jektivního, von Neumannovsky regulárního okruhu. 1
|
|
|
Zobecněná integrální vlastnost
Hrúzová, Jana ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce vychází z odborného článku C. Boura a A. Canteaut, Another View of the Division Property, který pojednává o dělící vlastnosti množin z Fn 2 . V této práci nejprve zopakujeme důležité pojmy a tvrzení o booleovských funkcích, polynomech a Reed-Mullerových kódech. Následně definujeme množinu parit množiny z Fn 2 . Pomocí množiny parit zjednodušíme dělící vlastnost a ukážeme, jak vypadají množiny splňující různé stupně dělící vlastnosti. Díky tomu budeme moci určit, jak se dělící vlastnost šíří substitučně-permutační sítí. 1
|
|
|
Cryptoanalysis of a Post-quantum Cryptography Algorithm
Štumpf, Daniel ; Hojsík, Michal (vedoucí práce) ; Příhoda, Pavel (oponent)
Národní institut standardů a technologie (NIST) v současnosti řídí standardizační proces pro postkvantové kryptografické primitivy. V závislosti na stavebních blocích šif- rovacích algoritmů je rozdělujeme do pěti kategorií. V první části této práce jsme popsali všech pět kategorií a porovnali jejich charakteristiky. Nejdůležitějším aspektem schémat pro NIST je bezpečnost proti klasickým i kvan- tovým protivníkům. V druhé části této práce se zabýváme kryptoanalýzou jedné z pěti kategorií (jmenovitě jsme vybrali kryptosystémy založené na mřížkách). Protože si mys- líme, že bezpečnostní analýza některých kandidátů druhého kola v rámci standardizač- ního projektu NIST není dostatečně popsána v jejich specifikačních dokumentech a ně- které známé útoky nejsou vůbec uvažovány, poskytujeme jednotnou bezpečnostní analýzu těchto schémat. Popsali jsme dva v současnosti známé útoky (primární a duální útoky) proti schématům založeným na mřížkách. Odhadli jsme složitost těchto dvou útoků proti kandidátům ve druhém kole tohoto standardizačního procesu a tyto hodnoty jsme po- rovnali s bezpečností, kterou tito kandidáti uvádějí ve svých specifikačních dokumentech. Ve většině případů se naše odhady shodují s odhady zveřejněnými ve specifikačních do- kumentech, a proto docházíme k závěru, že bezpečnostní odhady jednotlivých...
|
|
|
Krátké invertibilní prvky v cyklotomických okruzích
Kroutil, Jaroslav ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce vychází z odborného článku, který pojednává o kritériu invertibility prvků ve speciálně volených cyklotomických okruzích. V této práci nejprve zopakujeme důležité pojmy a tvrzení z algebry, jež budeme potřebovat. Následně se budeme zabývat existencí nekonečně mnoha prvočísel splňujících podmínky, které využijeme k ireducibilnímu rozkladu cyklotomických polynomů. Na základě těchto polynomů definujeme cyklotomický okruh, ve kterém v závěru práce dokážeme invertibilitu prvků v závislosti na velikosti jejich normy.
|
|
|
Kubická a bikvadradická reciprocita
Staško, Samuel ; Příhoda, Pavel (vedoucí práce) ; Krásenský, Jakub (oponent)
Hlavní motivací pro zkoumání kubické a bikvadratické reciprocity je rozhod- nout, zda mají kongruence x3 ≡ a (p) nebo x4 ≡ a (p), kde a ∈ Z, p prvočíslo, nějaké celočíselné řešení. Jádrem této práce je prostřednictvím postupně vybudo- vané teorie v okruzích Eisensteinových a Gaussových celých čísel dokázat zákony kubické a bikvadratické reciprocity. U obou těchto tvrzení se navíc podrobněji podíváme na speciální případy, ve kterých je nelze použít. To nás povede k od- vození tzv. doplňku k zákonu kubické (resp. bikvadratické) reciprocity. Nakonec ukážeme, jak lze tyto výsledky aplikovat na problém řešitelnosti zmíněných kon- gruencí. 1
|
|
|
Algoritmy pro faktorizaci čísel speciálního tvaru
Lorenc, Filip ; Příhoda, Pavel (vedoucí práce) ; Růžička, Pavel (oponent)
Bakalářská práce se zabývá třemi faktorizačními algoritmy - Pollardovou p-1 metodou, Williamsovou p+1 metodou a metodou eliptických křivek ECM. Cílem práce je algoritmy teoreticky popsat a poté je porovnat na konkrétních vstupech. U každého algoritmu popíšeme základní a rozšířenou verzi a potom odvodíme jejich časovou složitost. V první kapitole definujeme B-mocnost a B-hladkost čísla a uvedeme jejich odhady. Druhá, třetí a čtvrtá kapitola je o popisu algoritmů a v poslední kapitole porovnáváme jejich efektivitu a výkon. Část práce obsahuje základní teorii o eliptických křivkách, které se používají v ECM. K dispozici je i program obsahující tyto algoritmy.
|
|
|
Problém LWE a bezpečnost schémat pro výměnu klíče
Václavek, Jan ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Hrozba silného kvantového počítače vede ke snaze založit kryptosystémy na problémech, které budou těžké i pro kvantový počítač. V této práci si předsta- víme problém LWE, o kterém se předpokládá, že by takovým problémem mohl být. Nejprve si představíme mříže, které s problémem LWE úzce souvisí. Zave- deme základní pojmy, popíšeme mřížové problémy a vyřešíme cvičení týkající se pokrývajícího poloměru mříže. Poté definujeme problém LWE, představíme jeho varianty a ukážeme redukce dvou mřížových problémů na vhodnou variantu pro- blému LWE. K tomuto účelu definujeme pojem statistické vzdálenosti a dokážeme o něm tvrzení, která potřebujeme pro redukci. Nakonec ukážeme konkrétní vyu- žití problému LWE. Popíšeme schéma na výměnu klíče a naznačíme, jak dokázat jeho bezpečnost za předpokladu, že problém LWE je těžký. 1
|
|
|
Důkazy bezpečností hashovacích funkcí
Zpěváček, Marek ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Tato práce se zaměřuje na důkaz redukce přibližného SBP na SIS. Důkaz provedl již Miklós Ajtai v roce 1996 ve své přelomové práci, avšak jeho důkaz je místy často nejasný a některé kroky nejsou dostatečně rozepsány. Redukce je typu nejhorší případ převeden na průměrný případ. Před zmíněnou prací Ajtaie nebyla známa žádná redukce takového typu. Proto nám přijde vhodné se k důkazu vrátit a rozepsat všechny jeho kroky do většího detailu. Dále je v práci shrnuta složitost základních problémů na mřížkách. Na základě těchto složitostí a dokázané redukce je možné definovat hashovací funkce odolné vůči kolizím. Na takové funkce se tato práce také zběžně zaměřuje. 1
|
host ::
RSS.