|
|
Testování perfektních mocnin
Straková, Hana ; Stanovský, David (vedoucí práce) ; Jedlička, Přemysl (oponent)
Perfektní mocnina je takové přirozené číslo, které lze zapsat jako netriviální mocninu jiného přirozeného čísla. Přirozené číslo n tedy nazveme perfektní mocninou, pokud existují přirozená čísla x a k, obě větší než 2, taková, že n = x^k. Testy, zda je číslo perfektní mocnina, jsou důležité pro faktorizaci čísel nebo testy prvočíselnosti, které samy neumějí rozlišit, zda je vstupní číslo mocnina jiného čísla. Tato práce pojednává o dvou algoritmech na testování perfektních mocnin, prvním od E.Bacha & J. Sorensona a druhém od Daniela J. Bernsteina. Cílem práce je implementace algoritmů v jazyce C s pomocí knihovny GMP, srovnání teoretických výsledků pro jednotlivé algoritmy s praktickými měřeními a porovnání algoritmů mezi sebou z hlediska teoretického přístupu a rychlosti.
|
|
| |
|
|
Faktorizace polynomů nad konečnými tělesy
Straka, Milan ; Žemlička, Jan (vedoucí práce) ; Stanovský, David (oponent)
Nazcv prace: Faktorizace polynoinu nad konccnynii telesy Autor: Milan Straka Katcdra (ustav): Katcdra algebry Vedouci bakalarske prace: Mgr. Jan Zcmlicka, Ph.D. E-mail vedouciho: Jan.Zemlicka((hnff. cuni.cz Abstrakt: Cilem prace je prozkoumat problem rozkladu polynomn nad konecnym telc- scm na soucin ircducibilnich polynoinu. PopHanim nekolika algoritmu hledaji- cich tento rozklad se ukaze, ze tento problem je vzdy fcsitclny v polynornialnim case vzhleclem kc stupni polynomu a poctu prvku konecneho telcsa. U jeduoho z algoritnm je po])sana implenientace s vclnii clobrou asymptotic- kou casovou slozito.sti O(nLylD log c/}, kdc i\. jc stupen rozkladaneho polynuinn nad telesem « q prvky. Program pouzivajiei jcdnodnssi, ale prakticky rychlcjsi variantu tohoto algoritnm jc soucasti ])racc. Klicova slova: faktorizace, kouecna telesa, polynoniy, algoritmns Title: Factoring polynomials over finite fields Author: Milan Straka Department: Department of Algebra Supervisor: Mgr. Jan Zemlicka, Ph.D. Supervisor's e-mail address: Jan. Zcirilicka@mJJ.cum.cz Abstract: The goal of this work is to present the problem of the decomposition of a polyno- mial over a finite field into a product of irreducible polynomials. By describing algorithms solving this problem, we show that the decomposition can always be found in...
|
|
| |
|
|
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)
|
|
| |
|
|
Srovnání algoritmů pro kryptografii s veřejným klíčem
Mareš, Jiří ; Stanovský, David (vedoucí práce) ; Žemlička, Jan (oponent)
V předložené práci se zabýváme srovnáním základních algoritmů pro šifrování s veřejným klíčem - algoritmy RSA, Rabinovou a ElGamalovou metodou. Odvozujeme teoretickou složitost šifrování a dešifrování jednoho bloku a odvozujeme předpokládaný model chování při zdvojnásobení velikosti klíče. Rovněž provádíme praktická měření rychlosti jednotlivých metod na klíčích velikosti 64 - 4096 bitů a statisticky je vyhodnocujeme. U některých algoritmů uvádíme speciální případy a diskutujeme výhody a nevýhody a jejich praktické použití. Na závěr srovnáváme rychlosti jednotlivých algoritmů a porovnáváme naměřené výsledky s teoretickými předpoklady.
|
|
|
Polynomiální rovnice nad konečnými tělesy a algebraická kryptoanalýza
Seidl, Jan ; Stanovský, David (vedoucí práce) ; Drápal, Aleš (oponent)
Název práce: Polynomiální rovnice nad konečnými tělesy a algebraická kryptoanalýza Autor: Jan Seidl Katedra: Katedra algebry Vedoucí diplomové práce: doc. RNDr. David Stanovský, Ph.D., Katedra algebry Abstrakt: Předložená práce se zaobírá postupem algebraické kryptoanalýzy, při kterém je nejprve problém prolomení šifry převeden na problém nalezení řešení polynomiální soustavy rovnic a následně je problém nalezení řešení této rovnice převeden na problém SAT. Práce popisuje konkrétně metody, které umožňují převést problém prolomení šifry RC4 na problém SAT. Jed- notlivé metody byly naprogramovány v programovacím jazyce Mathematica a následně aplikovány na RC4 s délkou slova 2, 3. Pro nalezení splnitelného ohodnocení výsledné logické formule byl použit SAT-solver CryptoMiniSAT. V případě RC4 s délkou slova 2 bylo dosaženo nalezení řešení v rozpětí 0,09 až 0,34 sekundy, v případě RC4 s délkou slova 3 pak bylo dosaženo na- lezení řešení v rozpětí 1,10 až 1,23 sekundy. Klíčová slova: RC4, SAT, CryptoMiniSAT 1
|
|
| |
|
| |
host ::
RSS.