|
|
Algoritmy pro Minkowského součet mnohoúhelníků
Šimek, Daniel ; Patáková, Zuzana (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce se zabývá Minkowského součtem dvou nekonvexních mnoho- úhelníků v rovině, konkrétně pak popisem a porovnáním dvou metod pro výpočet Min- kowského součtu: rozkladové metody a konvoluční metody. V této práci jsou obě tyto metody blíže představeny, včetně potřebných definic a ilustrativních obrázků. V závě- rečné kapitole jsou pak obě metody porovnány za pomoci C++ knihovny CGAL na různých vstupech. 1
|
|
|
Bezpečné sdílené počítání modulo p^k
Struk, Martin ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Práce se zabývá odvětvím kryptografie zvaným bezpečné sdílené počítání, což je tech- nika, která umožňuje více stranám spolupracovat na výpočtu jediné funkce tak, že její vstupy zůstanou utajeny. Konkrétněji se práce zabývá bezpečným sdíleným počítáním nad okruhem celých čísel modulo pk . Práce začíná představením obecného principu pro- tokolů pro bezpečné sdílené počítání, po kterém následuje vybudování potřebné teorie nad komutativními okruhy, která bude v poslední části práce potřeba k popisu a pochopení konkrétního protokolu. 1
|
|
|
Řetězové zlomky v tělese p-adických čísel
Červenková, Eliška ; Příhoda, Pavel (vedoucí práce) ; Růžička, Pavel (oponent)
Tato práce se věnuje Rubanovu a Browkinovu rozvoji p-adických čísel do řetězového zlomku a jejich vlastnostem. Nejprve je zaveden pojem p-adických čísel a sepsaná po- třebná teorie. Následně je definován řetězový zlomek a jsou odvozeny podmínky konver- gence v reálných a p-adických číslech. Dále je v textu popsán Rubanův rozvoj do řetězo- vého zlomku a práce se zabývá jeho konečností. Součástí je popis algoritmu, díky kterému lze o konečnosti rozhodnout. Odvozen je i maximální počet kroků v tomto algoritmu. Pro Rubanův rozvoj dále platí, že je-li nekonečný, pak je periodický. V textu je periodicita včetně jejích vlastností blíže popsána. Práce se pak věnuje Browkinovu rozvoji do řetě- zového zlomku včetně důkazu, že tento rozvoj je pro racionální čísla konečný. Obsahem jsou i příklady ilustrující popsané vlastnosti obou rozvojů. 1
|
|
|
Tateova-Šafarevičova grupa eliptické křivky
Zvěřina, Adam ; Šťovíček, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato práce se zabývá Tateovou-Šafarevičovou grupou a jejím vztahem k racionál- ním bodům na křivce a jejímu ranku. Napřed definujeme pojem profinitní grupy a cha- rakterizujeme je jako Galoisovy grupy tělesových rozšíření. Potom definujeme Tateovu- Šafarevičovu grupu pomocí Galoisovy kohomologie a vysvětlíme její vztah k racionálním bodům křivky. Nakonec zformulujeme Birchovu-Swinnerton-Dyerovu domněnku, která dává do souvislosti rank eliptické křivky a řád její Tateovy-Šafarevičovy grupy. 1
|
|
|
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- žitelnosti se základními verzemi. Kromě několika známých variant prezentujeme vlastní návrhy jak kvadratického, tak číselného síta a podrobně analyzujeme jejich výhody či nevýhody. 1
|
|
|
Využití invertibilních prvků mřížky v ověření s nulovou znalostí
Kučerová, Karolína ; Žemlička, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Práce se zaměřuje na popis kryptografického protokolu, který se řadí do skupiny ově- řitelného šifrování, přesněji jde o metodu ověření s nulovou znalostí. Ověřitelné šifrování nám dovoluje dokázat vlastnosti určitého textu. Pokud je šifrovací schéma je bezpečné, nemělo by při důkazu dojít k prozrazení obsahu textu. Hlavním cílem metody je ověření znalosti soukromého klíče. Metodu lze využít k vytváření skupinových podpisů, předávání informací ve více krocích, nebo například k uschovávání klíčů. Je založena na složitosti okruhového-LWE šifrování v kombinaci s hledáním řešení soustav lineárních rovnic a využívá principu rejection sampling. Zkoumaná metoda spojuje principy dvou blíže po- psaných kryptografických metod a to okruhového LWE a metody. Využívá konstrukci faktorokruhů R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1
|
|
|
Local properties of modules
Lysoněk, Tomáš ; Hrbek, Michal (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato práce zavádí vlastnosti modulů - projektivitu a plochost relativní vzhledem ke třídám konečně prezentovaných modulů - které jsou zobecněním projektivity a čisté projektivity. Dále je podán důkaz ascentu a descentu těchto vlastností skrze homomor- fismy nekomutativních okruhů s jistými vlastnostmi, z nichž nejdůležitější je schopnost rozeznávat čisté epimorfismy. V relativním případě dokazujeme ascent a descent skrze ploché okruhové homomorfismy s touto vlastností. Nakonec jsou tyto výsledky aplikovány na situaci okruhových homomorfismů, které vznikají jako centrální rozšíření centrálních čistých a věrně plochých homomorfismů. 1
|
|
|
Structural and categorical description of classes of abelian groups
Dvořák, Josef ; Žemlička, Jan (vedoucí práce) ; Modoi, George Ciprian (oponent) ; Příhoda, Pavel (oponent)
Práce představuje výsledky týkajících se vlastností samomalosti a relativní malosti součinů v kategorii abelovských grup a Ab5-kategorií. Jsou představena kritéria relativní malosti abelovských grup a je podána charakterizace samoma- lých součinů konečně generovaných abelovských grup. Dále je vybudována teorie rozkladů v UD-kategoriích a v důsledku i v kategoriích S-aktů, přičemž tyto jsou následně užity ke zkoumání (samo)malosti S-aktů. Je podán strukturální popis kompaktních objektů ve dvou kategoriích S-aktů. Taktéž je zkoumána existence projektivních pokrytí v kategoriích S − Act a S − Act0 a pozornost je věnována problematice perfektních monoidů s nulou. 1
|
|
|
Gröbnerovy báze
Mašková, Kristýna ; Trlifaj, Jan (vedoucí práce) ; Příhoda, Pavel (oponent)
Gröbnerova báze je konkrétní množina generátorů ideálu v okruhu polynomů S = K[x1, . . . , xn]. Tento pojem je zaveden vzhledem k monickému uspořádání. V práci zave- deme tyto pojmy a představíme Buchbergerovo kritérium, které nám umožní efektivně ověřit, zda je množina generátorů Gröbnerova báze. Ukážeme Buchbergerův algoritmus, který nám z konečné množiny generátorů vytvoří Gröbnerovu bázi. Podíváme se na speciální případ lineárně homogenních ideálů, kdy lze Gröbnerovu bázi spočítat jednoduše Gaussovou eliminací. Nakonec tuto teorii rozšíříme na podmoduly volných modulů a stručně naznačíme, jak použít Gröbnerovy báze pro důkaz Hilbertovy věty o syzygiích. 1
|
|
|
Verifiable Delay Functions z Lucasových posloupností
Krňák, Tomáš ; Hubáček, Pavel (vedoucí práce) ; Příhoda, Pavel (oponent)
Lucasovy posloupnosti jsou konstantní rekurzivní celočíselné posloupnosti s dlouhou historií aplikací v kryptografii - používané jak pro návrh kryptografických schémat, tak při kryptoanalýze. V této práci představujeme ověřitelné zpožďovací funkce založené na sekvenční náročnosti výpočtu Lucasových posloupností v RSA grupě. Zaprvé ukážeme, že modulární Lucasovy poslopnosti jsou alespoň tak sekvenční, jako jsou klasické zpožďovací funkce založené na iterovaném modulárním mocnění představené Rivestem, Shamirem, and Wagnerem v kontextu tzv. time-lock puzzles. Navíc ne- nacházíme žádnou očividnou opačnou redukci, což nás přivádí k domněnce, že počítání modulárních Lucasových poslopností je ostře složitější než modulární iterované mocnění. Jinými slovy, námi kostruovaná zpoždovací funkce si zachová svoji sekvenčnost i v případě nalezení nového efektivnějšího algoritmu pro modulární iterováné mocnění. Zadruhé představíme praktickou konstrukci ověřitelné zpožďovací funkce založené na modulárních Lucasových posloupnostech. Naše konstrukce vychází z nedávné práce Pietrzaka (ITCS 2019) a využívá souvislost mezi problémem výpočtu modulárních Lu- casových posloupností a mocněním v příslušném tělesovém rozšíření. 1
|
host ::
RSS.