| Title: | Některé algoritmy pro prvočíselné rozklady |
| Other Titles: | Some methods for integer factorization |
| Authors: | Šuster, Zdeněk |
| Advisor: | Honzík Lukáš, PhDr. Ph.D. |
| Issue Date: | 2019 |
| Publisher: | Západočeská univerzita v Plzni |
| Document type: | diplomová práce |
| URI: | http://hdl.handle.net/11025/39197 |
| Keywords: | prvočíslo;prvočíselný rozklad;faktorizace dělením;pollardův rho algoritmus;pollardův p-1 algoritmus;eulerova metoda |
| Keywords in different language: | prime number;integer factorization;trial factorization;pollard´s rho algorithm;pollard´s p-1 algorithm;euler´s method |
| Abstract: | Jedním z cílů této práce je seznámení s prvočíselností a faktorizačních metod. Nejprve je vysvětlen důležitý pojem pro tuto práci, tj. prvočíslo, a také prvočíselný rozklad. Tyto pojmy hrají důležitou roli u faktorizačních metod pro nalezení prvočíselného rozkladu u celých čísel. V druhé kapitole jsou mezi popsanými faktorizačními metodami faktorizace dělením ("hrubá" síla), Pollardův rho algoritmus, Pollardův p - 1 algoritmus a Eulerova metoda. Některé z algoritmů lze využít i pro zvídavé žáky v učitelské praxi. K těmto metodám bylo v následující kapitole vypočteno několik ilustračních příkladů, které se snažili ukázat početní i časovou náročnost těchto algoritmů, ale také jejich možnosti pro zrychlení výpočtu i jejich úskalí. Během výpočtů byla použita řada sofistikovanějších zařízeních pro rychlejší výpočet příkladů, a to stolní kalkulátor TI - 92 Plus či webové prostředí WolframAlpha. Právě časová náročnost je podstatou poslední kapitoly, kde se zabývám pojmy jako složitost algoritmu a třídy složitosti, pomocí kterých můžeme porovnávat algoritmy právě z hlediska času jejich výpočtu. |
| Abstract in different language: | One of the aims of this thesis is to get acquainted with prime numbers and factorization methods. First, an important concept for this thesis, i.e. a prime number, is also explained, as well as a prime quote. These terms play an important role in factorization methods for finding prime numbers in integers. In the second chapter, there are described the following factoring methods: Trial Factorization, Pollard rho algorithm, Pollard p - 1 algorithm and Euler's method. Some of the algorithms can also be used for inquisitive pupils in teaching practice. Several illustrative examples have been computed in these chapters, which have attempted to show both the numerical and time demands of these algorithms, but also their possibilities for speeding up the calculations and their obstacles. During the calculations, a number of more sophisticated devices were used to quickly compute examples, such as the TI - 92 Plus Desktop Calculator and the WolframAlpha Web Environment. Time-consuming is the essence of the last chapter where I deal with concepts such as the complexity of the algorithm and the complexity class, by which we can compare the algorithms precisely in terms of the time of their calculation. |
| Rights: | Plný text práce je přístupný bez omezení. |
| Appears in Collections: | Diplomové práce / Theses (KMT) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Nektere metody pro prvociselne rozklady.pdf | Plný text práce | 1,24 MB | Adobe PDF | View/Open |
| hodnoceni vedouciho DP - Suster.pdf | Posudek vedoucího práce | 27,45 kB | Adobe PDF | View/Open |
| Posudek diplomove prace Suster.pdf | Posudek oponenta práce | 131,17 kB | Adobe PDF | View/Open |
| Suster protokol762.pdf | Průběh obhajoby práce | 306,62 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/39197Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.