Název: Algoritmy pro faktorizaci čísel speciálního tvaru
Překlad názvu: Algorithms for factorization of integers of particular form
Autoři: Lorenc, Filip ; Příhoda, Pavel (vedoucí práce) ; Růžička, Pavel (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: cze
Abstrakt: [cze] [eng]
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. 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.
Klíčová slova: ECM; faktorizace; Pollardova p-1 metoda; Williamsova p+1 metoda; ECM; factorization; Pollard's p-1 method; Williams's p+1 method

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/107772

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-398343


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce