|
| |
|
|
Solving diophantine equations by factorization in number fields
Hrnčiar, Maroš ; Kala, Vítězslav (vedoucí práce) ; Příhoda, Pavel (oponent)
Název práce: Řešení diofantických rovnic rozkladem v číselných tělesech Autor: Bc. Maroš Hrnčiar Katedra: Katedra algebry Vedoucí diplomové práce: Mgr. Vítězslav Kala, Ph.D., Mathematisches Institut, Georg-August Universität Göttingen Abstrakt: Problém řešitelnosti diofantických rovnic je jedním z nejstarších ma- tematických problémů v historii. Postupně se vyvinuly různé přístupy k řešení určitých typů rovnic, z nichž se v práci zabýváme převážně metodou využívající faktorizaci v algebraickém číselném tělese. Myšlenkou této metody je vyjádřit rovnici ve tvaru L = yn , kde levá strana L je součin typicky lineárních fak- torů s koeficienty v daném číselném tělese. Při splnění několika předpokladů po- tom můžeme každý z faktorů napsat jako n-tou mocninu. Klíčovou roli při apli- kaci metody hraje struktura číselných těles, proto neoddělitelnou součást práce tvoří přehled algebraické teorie čísel. Kromě výkladu obecné teorie jsou zde uve- dené i výpočty v jednotlivých kvadratických a kubických tělesech popisující jejich vlastnosti. Hlavním předmětem práce je však řešení konkrétních úloh. Například v rovnici x2 + y2 = z3 se potýkáme s netriviálními společnými děliteli faktorů v...
|
|
| |
|
| |
|
| |
|
| |
|
|
Smartův algoritmus
Sladovník, Tomáš ; Příhoda, Pavel (vedoucí práce) ; Šťovíček, Jan (oponent)
Problém diskrétního logaritmu je jedním z pilířů asymetrické kryp- tografie a jeho použití na eliptických křivkách nad konečným prvočíselným tělesem se jeví jako velice efektivní. Tato práce se zabývá jeho řešením na eliptických křivkách, jejichž velikost je rovna velikosti onoho tělesa. Cílem této práce je se- stavit funkční algoritmus, který bude schopen řešit tento problém v lineárním čase podle počtu grupových operací a ověřit jeho správnost. K vytvoření algo- ritmu je potřeba pracovat s p-adickými čísly, zavést základy teorie formálních grup, formálního logaritmu a zavést podgrupy eliptických křivek nad p-adickými čísly. Ukáže se, že použití tohoto typu křivek je pro kryptografické účely naprosto nevhodné, a že tyto křivky nejsou bezpečné. 1
|
|
|
Pokročilé metody hledání diskrétního logaritmu
Matocha, Vojtěch ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Mějme konečnou cyklickou grupu G generovanou prvkem g. Problém diskrétního logaritmu, tedy pro zadané y nalézt přirozené číslo x splňující g^x = y, představuje jeden ze základních pilířů moderních kryptografických transformací. Ve své práci podáváme přehled algoritmů, které se pro výpočet diskrétního logaritmu používají, včetně v současnosti nejrychlejšího známého algoritmu pro multiplikativní grupu konečného tělesa: funkčního síta. Kromě funkčního síta se podrobněji zabýváme index kalkulem a jeho optimalizacemi: Coppersmithovým algoritmem a polynomiálním sítem. Hlavním přínosem práce je implementace funkčního síta v jazyce C a její aplikace na konkrétní vstupy.
|
|
| |
|
|
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
|
host ::
RSS.