Original title:
Složitost některých faktorizačních algoritmů
Translated title:
Complexity of some factoring algorithms
Authors:
Štěpánek, Vilém ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee) Document type: Bachelor's theses
Year:
2016
Language:
cze Abstract:
[cze][eng] Práce se věnuje odhadu složitosti běhu algoritmu pro faktorizaci celého čísla použitím metody ECM. Nejprve jsou nastíněny základní vlastnosti eliptických křivek nad konečným tělesem a uvedeny dvě věty, na kterých se daná problematika zakládá. Následně jsou provedeny potřebné odhady různými konstantami a nastíněn princip fungování algoritmu ECM pro faktorizaci celého čísla. Poté je ukázána odhadovaná složitost algoritmu ECM a na závěr je rozvedena implementace faktorizačního algoritmu ECM.Thesis is devoted to estimate complexity of algorithms running time for factorization of integer using ECM. Firstly, basic characteristic of elliptic curves over finite fields are sketched and presented two theorems on which this problematic is based. Consequently, there are given necessary estimates by some constants and ECM algorithms behavior is sketched. After that there is shown estimated complexity of algorithm ECM and finally there is specified implementation of factoring algorithm ECM.
Keywords:
ECM Factorization Elliptic curves; ECM Faktorizace Eliptické křivky
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/84487