|
|
Prosívání ve faktorizačních algoritmech
Staško, Samuel ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Kvadratické a číselné síto jsou dvě tradiční faktorizační metody. Uvádíme zde princip fungování obou těchto algoritmů, přičemž se zaměřujeme především na výpočet asympto- tické složitosti. Největší důraz klademe na rozbor prosívací fáze. Hlavním cílem práce je však popis různých modifikací, odhad jejich časové složitosti a porovnání praktické využi- telnosti se základními verzemi. Kromě toho prezentujeme vlastní variantu kvadratického síta, která má v některých oblastech oproti ostatním známým návrhům poměrně velké výhody. 1
|
|
|
Modules over Gorenstein rings
Pospíšil, David ; Trlifaj, Jan (vedoucí práce) ; Příhoda, Pavel (oponent) ; Herbera Espinal, Dolors (oponent)
Název práce: Moduly nad Gorensteinovými okruhy Autor: David Pospíšil Katedra: Katedra algebry Vedoucí disertační práce: Prof. RNDr. Jan Trlifaj, DSc. E-mail vedoucího: trlifaj@karlin.mff.cuni.cz Abstrakt: Disertační práce zahrnuje mé dosavadní příspěvky ke klasifikaci (ko)vychylujících modulů a tříd nad Gorensteinovými okruhy. Oproti původnímu záměru se v ní dokonce podařilo provést klasifikaci (ko)vychylujících tříd pro obecnější případ komutativních noetherovských okruhů (viz. třetí článek této disertace). Disertace se sestává z úvodu a tří článků se spoluautory. První článek (publikovaný v Contemp. Math.) ob- sahuje klasifikaci všech (ko)vychylujících modulů a tříd nad 1-Gorenstenovými komutativními okruhy. Druhý článek (publikovaný v J. Algebra) obsahuje klasifikaci všech vychylujících tříd nad regulárními okruhy Krullovy dimenze 2 a též klasifikaci všech vychylujících modulů v lokálním případě. Konečne třetí článek (preprint) obsahuje klasifikaci všech (ko)vychylujících tříd a také torzních párů nad obecnými komutativními noetherovskými okruhy. Všechny tyto klasifikace jsou popsány pomocí podmnožin spektra okruhu a asocio- vaných prvoideálů modulů. Klíčová slova: (ko)vychylující modul,...
|
|
|
Analysis of the stream cipher QUAD
Čurilla, Marcel ; Holub, Štěpán (vedoucí práce) ; Příhoda, Pavel (oponent)
Název práce: Analýza proudové šifry QUAD Autor: Marcel Čurilla Katedra: Katedra algebry Vedoucí diplomové práce: doc. Mgr. Štěpán Holub, Ph.D. Abstrakt: Prúdová šifra QUAD bola predstavená na Eurocrypte autormi Côme Ber- bain, Henri Gilbert a Jacques Patarin [1]. Ukázali redukciu tejto šifry na problém riešenia m kvadratických rovníc n premenných nad konečným telesom známy, ako MQ problém. Pre zjednodušenie, autori uvažovali len prípad telesa GF(2). V tejto práci predstavím túto prúdovú šifru. Uvidiem dôkaz (redukciu) bezpečnosti šifry QUAD na MQ problém nad l'ubovol'ným konečným telesom GF(q). Popíšem základné metódy pre riešenie systému kvadratických rovníc nad konečným telesom, linearizáciu a reline- arizáciu. Podrobnejšie sa budem venovat' algoritmu XL, momentálne najrýchlejšiemu algoritmu na riešenie kvadratických systémov. V analýze šifry QUAD ukážem pre ktoré instancie je šifra QUAD prelomitel'ná a naopak pre ktoré instancie je bezpečnost' zaručená. Klíčová slova: prúdová šifra , QUAD, MQ problém, algoritmus XL 1
|
|
| |
|
| |
|
|
Kombinatorická teorie grup v kryptografii
Ferov, Michal ; Příhoda, Pavel (vedoucí práce) ; Růžička, Pavel (oponent)
V předkládané práci se zabýváme aplikací rozhodovacích problémů z kombinatorické teorie grup v kryptografii, konkrétně protokolem Shpilrain- Zapata. Formálně dokážeme, že grupy s malým krácením slouží jako vhodná platforma pro získávání páru soukromý-veřejný klíč, protože problém slov v nich lze řešit v lineárním čase a jsou generické. Dále se zabýváme složitostí útoku hrubou silou a ukážeme, že protokol je po teoretické stránce odolný vůči útočníkovi s libovolnou výpočetní sílou.
|
|
|
Constructions of Commutative Semirings and Radical Rings
Korbelář, Miroslav ; Kepka, Tomáš (vedoucí práce) ; Němec, Petr (oponent) ; Příhoda, Pavel (oponent)
V této disertaci se budeme zabývat konstruktivními metodami aplikovanými na komutativní polookruhy a komutativní radikálové okruhy. V kapitole 2 budeme studovat třídu komutativních subdiretně ireducibilních radikálových okruhů. Uvedeme několik konstrukčních přístupů a pomocí reflexe z kategorie komutativních okruhů do kategorie komutativních radikálových okruhů odvodíme řadu příkladů s různými vlastnostmi. Ukážeme, že okruh S 2 S je noetherovský právě když je konečný. Dále uvedeme částečné výsledky v klasifikaci faktorů okruhů v S podle monolitu. V kapitole 3 pomocí p-prvočíselných valuací každému podpolookruhu v Q+ přiřadíme množinu jeho characteristických posloupností. Nalezneme a klasifikujeme všechny maximální podpolookruhy kladných racionálních čísel a ukážeme, že každý vlastní podpolookruh v Q+ je obsažen v nějakém z nich. Tento výsledek byl publikován v [16]. V kapitole 4 zkonstruujeme, použitím metod z kapitoly 4, novou širokou podtřídu třídy CongSimp všech vlastních kongruenčně jednoduchých podpolookruhřu v Q+, klasifikujeme všechny maximální prvky v CongSimp a ukážeme, že každý prvek CongSimp je obsažen alespoň v jednom z nich. V kapitole 5 nalezneme ekvivalentní podmínku pro to, aby polookruh Q+[ ] C, 2 C, byl obsažen v nějakém parapolotělese v C a provedeme klasifikaci pro případ, kdy je...
|
|
|
Singular points of algebraic varieties
Vančura, Jiří ; Příhoda, Pavel (vedoucí práce) ; Šťovíček, Jan (oponent)
Tato práce je úvodem do zkoumání sigularit alebraických variet. V první kapitole uvádíme základní definice a věty pro zkoumání singularit. Nejprve definujeme algebraické variety a jim odpovídající ideály, také vysvětlujeme pojem Krullovy dimenze. Dále se zaměřujeme na lokální vlastnosti variet. Ve druhé kapitole nejprve detailně rozebíráme pojem singularity, uvádíme metody, pomocí kterých můžeme singularity hledat. Poté dokážeme dvě tvrzení o tvaru a dimenzi singularit. Ve druhé části dokazujeme některá tvrzení o dělitelých nuly, ta nám umožní definovat Cohen-Macaulayovy a Gorensteinovy okruhy. Pomocí nich pak hrubě klasifikujeme singularity algebraických variet.
|
|
| |
|
|
Algebraic proofs of Dirichlet's theorem on arithmetic progressions
Čech, Martin ; Kala, Vítězslav (vedoucí práce) ; Příhoda, Pavel (oponent)
Dirichletova věta o aritmetických posloupnostech říká, že každá aritmetická posloupnost an = kn + pro nesoudělná čísla k, obsahuje nekonečně mnoho prvočísel. Původní důkaz této věty byl analytický a využíval mnoho neele- mentárních metod. Cílem této práce je najít nutné a postačující podmínky, za kterých může existovat elementárnější algebraický důkaz této věty a v těchto případech větu dokázat. 1
|
host ::
RSS.