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

• Název práce v češtině: Algoritmy pro faktorizaci čísel speciálního tvaru
• Název v anglickém jazyce: Algorithms for factorization of integers of particular form
• Klíčová slova: ECM, Pollardova p-1 metoda, Williamsova p+1 metoda, faktorizace
• Klíčová slova anglicky: ECM, Pollard's p-1 method, Williams's p+1 method, factorization
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Pavel Příhoda, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 12.10.2018
• Datum zadání: 12.10.2018
• Datum potvrzení stud. oddělením: 22.11.2018
• Datum a čas obhajoby: 19.06.2019 10:00
• Datum odevzdání elektronické podoby: 15.05.2019
• Datum odevzdání tištěné podoby: 17.05.2019
• Datum proběhlé obhajoby: 19.06.2019
• Oponenti: doc. Mgr. Pavel Růžička, Ph.D.

Zásady pro vypracování

Student se bude zabývat algoritmy pro faktorizaci čísel dělitelných prvočíslem speciálního tvaru. Zaměří se zejména na algoritmy předpokládající, že vstup je dělitelný prvočíslem p, kde je buď p-1,p+1,p^2+p+1 atd součin malých prvočísel. Práce by měla provést praktické srovnání navržených algoritmů s univerzálnější metodou ECM. V případě potřeby je možné studovat další faktorizační algoritmy, například zobecnění podle Bacha a Shallita.

Seznam odborné literatury

Bach, E.; Shallit, J. Factoring with Cyclotomic Polynomials. Mathematics of Computation. American Mathematical Society. 52(1989) (185): 201–219.

Crandall R.; Pomerance C. Prime numbers. A computational perspective. Second edition. Springer, New York, 2005.

Williams, H. C. A p+1 method of factoring. Mathematics of Computation, 39(1982) (159): 225–234.