Tato práce se zabývá prvočísly, testy prvočíselnosti a faktorizací celých čísel. V části prvočíselných testů obsahuje ukázky použití Fermatova a Eulerova prvočíselného testu, AKS testu a Miller-Rabinova testu. Následují klasické metody faktorizace, tedy opakované dělení, Fermatova metoda faktorizace, Eulerova metoda faktorizace, Euklidův algoritmus. V části moderní faktorizační metody jsou umístěny Pollardovy faktorizační metody, SQUFOF, CFRAC, kvadratické síto a ECM. Práce také obsahuje ukázky testů prvočíselnosti v různých matematických softwarech.
Anotace v angličtině
This thesis deals with prime numbers, primality proving and integer factorization. The first part deals with Primality proving, which includes examples of using Fermat´s primality test, Euler´s primality test, AKS test and Miller-Rabin´s test. The following part is devoted to classical methods of factorization, i.e. trial division, Fermat´s factoring method, Euler´s factoring method and Euclid´s algorithm. The next part focuses on modern methods of factorization, i.e. Pollard´s factoring methods, SQUFOF, CFRAC, quadratic sieve and ECM. This thesis also includes samples of primality proving in various mathematical software.
Klíčová slova
prvočíslo, pseudoprvočíslo, prvočíselný test, Fermatův prvočíselný test, Eulerův prvočíselný test, AKS, Miller-Rabinův test, faktorizace, klasické metody faktorizace, Fermatova faktorizační metoda, Eulerova faktorizační metoda, postupné dělení, moderní metody faktorizace, Pollardova metoda, ECM, RSA
Tato práce se zabývá prvočísly, testy prvočíselnosti a faktorizací celých čísel. V části prvočíselných testů obsahuje ukázky použití Fermatova a Eulerova prvočíselného testu, AKS testu a Miller-Rabinova testu. Následují klasické metody faktorizace, tedy opakované dělení, Fermatova metoda faktorizace, Eulerova metoda faktorizace, Euklidův algoritmus. V části moderní faktorizační metody jsou umístěny Pollardovy faktorizační metody, SQUFOF, CFRAC, kvadratické síto a ECM. Práce také obsahuje ukázky testů prvočíselnosti v různých matematických softwarech.
Anotace v angličtině
This thesis deals with prime numbers, primality proving and integer factorization. The first part deals with Primality proving, which includes examples of using Fermat´s primality test, Euler´s primality test, AKS test and Miller-Rabin´s test. The following part is devoted to classical methods of factorization, i.e. trial division, Fermat´s factoring method, Euler´s factoring method and Euclid´s algorithm. The next part focuses on modern methods of factorization, i.e. Pollard´s factoring methods, SQUFOF, CFRAC, quadratic sieve and ECM. This thesis also includes samples of primality proving in various mathematical software.
Klíčová slova
prvočíslo, pseudoprvočíslo, prvočíselný test, Fermatův prvočíselný test, Eulerův prvočíselný test, AKS, Miller-Rabinův test, faktorizace, klasické metody faktorizace, Fermatova faktorizační metoda, Eulerova faktorizační metoda, postupné dělení, moderní metody faktorizace, Pollardova metoda, ECM, RSA
Prostudovat základní fakta o prvočíslech, testy prvočíselnosti, pseudoprvočísla.
Základní algoritmy pro faktorizaci přirozených čísel. Ukázky výpočtů
v programu Mathematica, příp. v dalších prostředcích počítačové algebry.
1. Prvočísla - úvodní informace, klasické výsledky. Testy prvočíselnosti.
2. p-pseudoprvočísla, příklady silnějších prvočíselných testů, ukázky
výpočtů v programu Mathematica.
3. Metoda opakovaného dělení. Fermatova a Eulerova faktorizační metoda,
příp. další klasické faktorizační metody. Moderní faktorizační metody.
Rozvržení práce:
1. Seznámení s literaturou knižní i časopiseckou, překlady textů - do 30. 6. 2014
2. Příprava konceptu DP (včetně výpočetních ukázek v programu Mathematica)
- do 31. 12. 2014
3. Závěrečné úpravy a definitivní uzavření textu - do 31. 3. 2015
Zásady pro vypracování
Prostudovat základní fakta o prvočíslech, testy prvočíselnosti, pseudoprvočísla.
Základní algoritmy pro faktorizaci přirozených čísel. Ukázky výpočtů
v programu Mathematica, příp. v dalších prostředcích počítačové algebry.
1. Prvočísla - úvodní informace, klasické výsledky. Testy prvočíselnosti.
2. p-pseudoprvočísla, příklady silnějších prvočíselných testů, ukázky
výpočtů v programu Mathematica.
3. Metoda opakovaného dělení. Fermatova a Eulerova faktorizační metoda,
příp. další klasické faktorizační metody. Moderní faktorizační metody.
Rozvržení práce:
1. Seznámení s literaturou knižní i časopiseckou, překlady textů - do 30. 6. 2014
2. Příprava konceptu DP (včetně výpočetních ukázek v programu Mathematica)
- do 31. 12. 2014
3. Závěrečné úpravy a definitivní uzavření textu - do 31. 3. 2015
Seznam doporučené literatury
Crandall, R., Pomerance, C. B. Prime Numbers. A Computational
Perspective. 2. vydání, Springer, 2005.
Childs, L. A Concrete Introduction to Higher Algebra.
2. vydání, Springer, 2009.
Další knižní a časopisecké prameny, zdroje na Internetu,
manuál k počítačovému programu Mathematica.
Seznam doporučené literatury
Crandall, R., Pomerance, C. B. Prime Numbers. A Computational
Perspective. 2. vydání, Springer, 2005.
Childs, L. A Concrete Introduction to Higher Algebra.
2. vydání, Springer, 2009.
Další knižní a časopisecké prameny, zdroje na Internetu,
manuál k počítačovému programu Mathematica.