|
Testování perfektních mocnin
Straková, Hana ; Jedlička, Přemysl (oponent) ; Stanovský, David (vedoucí práce)
Perfektní mocnina je takové přirozené číslo, které lze zapsat jako netriviální mocninu jiného přirozeného čísla. Přirozené číslo n tedy nazveme perfektní mocninou, pokud existují přirozená čísla x a k, obě větší než 2, taková, že n = x^k. Testy, zda je číslo perfektní mocnina, jsou důležité pro faktorizaci čísel nebo testy prvočíselnosti, které samy neumějí rozlišit, zda je vstupní číslo mocnina jiného čísla. Tato práce pojednává o dvou algoritmech na testování perfektních mocnin, prvním od E.Bacha & J. Sorensona a druhém od Daniela J. Bernsteina. Cílem práce je implementace algoritmů v jazyce C s pomocí knihovny GMP, srovnání teoretických výsledků pro jednotlivé algoritmy s praktickými měřeními a porovnání algoritmů mezi sebou z hlediska teoretického přístupu a rychlosti.
|