velikost textu

Algoritmy pro faktorizaci čísel speciálního tvaru

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Algoritmy pro faktorizaci čísel speciálního tvaru
Název v angličtině:
Algorithms for factorization of integers of particular form
Typ:
Bakalářská práce
Autor:
Bc. Filip Lorenc
Vedoucí:
Mgr. Pavel Příhoda, Ph.D.
Oponent:
Mgr. Pavel Růžička, Ph.D.
Id práce:
206878
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra algebry (32-KA)
Program studia:
Matematika (B1101)
Obor studia:
Matematika pro informační technologie (MMIT)
Přidělovaný titul:
Bc.
Datum obhajoby:
19. 6. 2019
Výsledek obhajoby:
Velmi dobře
Jazyk práce:
Čeština
Klíčová slova:
ECM, Pollardova p-1 metoda, Williamsova p+1 metoda, faktorizace
Klíčová slova v angličtině:
ECM, Pollard's p-1 method, Williams's p+1 method, factorization
Abstrakt:
Bakalářská práce se zabývá třemi faktorizačními algoritmy - Pollardovou p-1 metodou, Williamsovou p+1 metodou a metodou eliptických křivek ECM. Cílem práce je algoritmy teoreticky popsat a poté je porovnat na konkrétních vstupech. U každého algoritmu popíšeme základní a rozšířenou verzi a potom odvodíme jejich časovou složitost. V první kapitole definujeme B-mocnost a B-hladkost čísla a uvedeme jejich odhady. Druhá, třetí a čtvrtá kapitola je o popisu algoritmů a v poslední kapitole porovnáváme jejich efektivitu a výkon. Část práce obsahuje základní teorii o eliptických křivkách, které se používají v ECM. K dispozici je i program obsahující tyto algoritmy.
Abstract v angličtině:
This bachelor thesis deals with three factorization algorithms - Pollard p-1 method, Williams p+1 method and elliptic curve method ECM. This work aims to describe these algorithms theoretically and then compare them on real inputs. For each algorithm we describe its basic and extended version and then we derive their time complexity. In the first chapter we define B-powersmooth and B-smooth number and we state their approximation. The second, third and fourth chapter is about description of algorithms and in the last chapter we compare their effectiveness and performance. A part of the work contains basic theory about elliptic curves, which is necessary in ECM. There is also included a program containing all these algorithms.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Filip Lorenc 1.26 MB
Stáhnout Příloha k práci Bc. Filip Lorenc 27.92 MB
Stáhnout Abstrakt v českém jazyce Bc. Filip Lorenc 211 kB
Stáhnout Abstrakt anglicky Bc. Filip Lorenc 208 kB
Stáhnout Posudek vedoucího Mgr. Pavel Příhoda, Ph.D. 54 kB
Stáhnout Posudek oponenta Mgr. Pavel Růžička, Ph.D. 51 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. David Stanovský, Ph.D. 152 kB