|
| |
|
|
Generování polynomů pro číselné síto
Pejlová, Anežka ; Drápal, Aleš (vedoucí práce) ; Příhoda, Pavel (oponent)
Název práce: Generování polynomů pro číselné síto Autor: Anežka Pejlová Katedra: Katedra algebry Vedoucí diplomové práce: prof. RNDr. Aleš Drápal, CSc., DSc., Katedra algebry Abstrakt: V této práci se zaměřujeme zejména na Kleinjungův algoritmus pro generování polynomů v rámci obecného číselného síta, což je v součas- nosti nejefektivnější faktorizační algoritmus. Obecně užívané postupy jsou popsány s důrazem na vysvětlení, které části lze rigorózně dokázat a které jsou motivovány pouze heuristicky. Přínosem práce je také přiložená imple- mentace Kleinjungova algoritmu vyvinutá v rámci projektu NFS vedeného na Katedře algebry. Empirická data získaná z této implementace podpírají vhodnost některých popsaných heuristik. Klíčová slova: Číselné síto, Kleinjungův algoritmus
|
|
|
Modulární a p-adické kódy
Sobotka, Miloslav ; Šťovíček, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Název práce: Modulární a p-adické kódy Autor: Bc. Miloslav Sobotka Katedra: Katedra algebry Vedoucí diplomové práce: RNDr. Jan Šťovíček, Ph.D., Katedra algebry, MFF UK Abstrakt: Cílem práce bylo studium modulárních kódů nad okruhy Zpe a kódů p-adických. Motivací byla představa posloupnosti kódů nad do sebe vnořenými okruhy Zpe , kdy kódy nad menšími okruhy mají tu vlastnost, že je lze získat z kódu nad vyšším okruhem operací modulo. Naopak při budování této posloup- nosti volíme zdvihy tak, aby tato podmínka zůstala zachována. Tento koncept vede k celé řadě otázek týkajících se kvality zdvižených, či řekněme snížených kó- dů, od zachování parametrů kódů, přes samodualitu a cykličnost až po studium chování váhového výčtu. Klíčová slova: modulární kód, p-adický kód, teorie invariantů, váhový výčet, MacWilliamsové identita Title: Modular and p-adic codes Author: Bc. Miloslav Sobotka Department: Department of Algebra Supervisor: RNDr. Jan Šťovíček, Ph.D., Department of Algebra, MFF UK Abstract: The aim of this thesis was to study modular codes over rings Zpe and p-adic codes. The motivation was the idea of a sequence of codes over nested rings Zpe , where the codes over smaller rings are obtained from the codes over larger rings using the modulo operation. Conversely, when constructing such a sequence we choose...
|
|
|
Number Field Sieve for Discrete Logarithm
Godušová, Anna ; Jedlička, Přemysl (vedoucí práce) ; Příhoda, Pavel (oponent)
Mnoho dnešních kryptografických systémů, jako například protokol Diffie- Hellman, je založených na problému diskrétního logaritmu. Síto v číselném tělese je algoritmus řešící faktorizaci velkých celých čísel, nové poznatky ale ukazují, že může být použit i na problém diskrétního logaritmu. V této práci studujeme síto v číselném tělese pro diskrétní logaritmus a porovnáváme ho se sítem v číselném tělese pro faktorizaci. Oba algoritmy jsou založeny na stejném principu, ale v jednotlivých krocích nalézáme velké rozdíly. 1
|
|
| |
|
|
Lineární kódy nad okruhy
Kobrle, Tomáš ; Šťovíček, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato diplomová práce se zaměřuje na speciální typ okruhů nazývaný algebry cest s cílem definovat a popsat lineární kódy nad těmito okruhy. Algebra cest je definována pomocí grafické struktury tak zvaných quiverů, jejich struktura se pak dále přenáší i na moduly algeber cest. Samotné kódy jsou definovány nad nerozložitelnými injektivními moduly algeber cest s ohledem na nedávné výsledky z teorie kódů nad okruhy. Takto definované kódy nám umožňují studovat parametry a verze základních tvrzení z teorie lineárních kódů na tělesy pro kódy nad okruhy. Zmíněná tvrzení se týkají duálních kódů a s nimi spjatou MacWilliams identitou následovaný tvrzením o ekvivalenci kódů. Nakonec se vracíme k algebrám cest s popisem způsobu, jak je lze udělat použitelné v teorii kódů nad okruhy.
|
|
|
Složitost některých faktorizačních algoritmů
Štěpánek, Vilém ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Práce se věnuje odhadu složitosti běhu algoritmu pro faktorizaci celého čísla použitím metody ECM. Nejprve jsou nastíněny základní vlastnosti eliptických křivek nad konečným tělesem a uvedeny dvě věty, na kterých se daná problematika zakládá. Následně jsou provedeny potřebné odhady různými konstantami a nastíněn princip fungování algoritmu ECM pro faktorizaci celého čísla. Poté je ukázána odhadovaná složitost algoritmu ECM a na závěr je rozvedena implementace faktorizačního algoritmu ECM.
|
|
|
Ideal lattices in cryptography
Vyhnalová, Sára ; Kala, Vítězslav (vedoucí práce) ; Příhoda, Pavel (oponent)
Práca sa venuje špeciálnym typom mriežok, a to ideálovým, cyklickým a NTRU mriežkam. Konkrétne ide o rozšírenie a zovšeobecnenie článku od autorov Ding a Lindner s názvom Identifying Ideal Lattices. Okrem algo- ritmu na identifikáciu ideálových mriežok práca obsahuje aj názorné príklady a detailnejšie prepracované dôkazy tvrdení, na ktorých sa algoritmus za- kladá. V sekcii s názvom Lattice Isomorphism predkladáme taktiež dôkaz zovšeobecnenej vety z článku. Ďalšie tvrdenie, nadväzujúce na vetu o identi- fikovaní ideálových mriežok, dokazujeme pre prípad NTRU mriežok, pričom úvahy dop'lňame príkladmi. Záverečnou čast'ou práce je kapitola o aplikáciách v kryptografii, ktorej súčast'ou je hashovacia funkcia založená na ideálových mriežkach. Poskytujeme tu aj stručný prehl'ad kryptografických algoritmov, ktoré využívajú NTRU mriežky.
|
|
|
The theorem about 27 lines
Till, Daniel ; Šťovíček, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
V tejto práci dokážeme, že na každej nesingulárnej kubickej ploche nad al- gebraicky uzavretým telesom charakteristiky rôznej od dvoch existuje práve 27 rôznych priamok. Najprv sa budeme venovať afinným algebraickým varietám a ich ideálom. Dokážeme si Hilbertovu vetu o nulácha a zavedieme morfizmy medzi afinnými algebraickými varietami. Potom sa presunieme k projektívnym alge- braickým varietám a ich ideálom. Zavedieme morfizmy medzi projektívnymi va- rietami a názvoslovia pre vybrané typy projektívnych variet. Dokážeme pomocné tvrdenia o prieniku dvoch rôznych priamok na projektívnej rovine, respektíve priamky a roviny v P3 K. Taktiež definujeme pojmy ako dotyčnicový priestor k variete v danom bode, singularita nadplochy a ireducibilná varieta. Následne sa presunieme do P3 K, kde dokážeme existenciu 27 rôznych priamok na ľubovoľnej nesingulárnej kubickej ploche. Tento dôkaz urobíme tak, že najprv dokážeme, že na takejto ploche existuje priamka a potom skonštruujeme všetkých 27 priamok vzájomnými vzťahmi. 1
|
|
|
Význačné prvky grupových okruhů
Procházková, Zuzana ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Název práce: Význačné prvky grupových okruhů Autor: Bc. Zuzana Procházková Katedra: Katedra algebry Vedoucí diplomové práce: doc. Mgr. et Mgr. Jan Žemlička, Ph.D., Katedra algebry Abstrakt: Tato diplomová práce se zabývá hledáním idempotentů v grupových okruzích. Jsou v ní popsány tři postupy hledání idempotentů v totálně rozložitel- ném grupovém okruhu a poslední kapitola popisuje pokusy o hledání idempotentů v grupovém okruhu, který nemusí být totálně rozložitelný. První postup využívá reprezentaci a charaktery grupy. Druhý postup hledá idempotenty pomocí Shodo- vých párů grupy. Třetí postup zvedá idempotenty z faktorokruhu pomocí CNC systémů ideálů, který zobecňuje dlouho známé zvedání idempotentů pomocí nil- potentního ideálu, a je zde rozšířen na grupové okruhy, které tvoří nekomutativní grupa a nekomutativní okruh. iii
|
host ::
RSS.