Original title: Testování perfektních mocnin
Translated title: Testing perfect powers
Authors: Straková, Hana ; Jedlička, Přemysl (referee) ; Stanovský, David (advisor)
Document type: Master’s theses
Year: 2008
Language: cze
Abstract: [cze] [eng]
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. A positive integer n is a perfect power if there exist integers x and k, both at least 2, such that n = x^k. Perfect power testing is important as preprocessing for number factorization and prime number testing, because many algorithms for that are not able to distinguish between prime number and power of prime number, so it is necessary to test it by perfect power tests. This thesis includes comparison of two algorithms for perfect power testing, one by Daniel J. Bernstein and the other by E. Bach & J. Sorenson. The goal is to implement described algorithms in C language with GMP library for multiple-precision arithmetics, to compare the theoretical results and running times of implemented algorithms.

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/14834

Permalink: http://www.nusl.cz/ntk/nusl-290957


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses