Testování perfektních mocnin
| Thesis title in Czech: | Testování perfektních mocnin |
|---|---|
| Thesis title in English: | Testing perfect powers |
| Academic year of topic announcement: | 2006/2007 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. RNDr. David Stanovský, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.10.2006 |
| Date of assignment: | 30.10.2006 |
| Date and time of defence: | 26.05.2008 00:00 |
| Date of electronic submission: | 26.05.2008 |
| Date of submission of printed version: | 26.05.2008 |
| Date of proceeded defence: | 26.05.2008 |
| Opponents: | doc. RNDr. Přemysl Jedlička, Ph.D. |
| Guidelines |
| Přirozené číslo se nazývá perfektní mocninou, pokud jej lze napsat jako netriviální mocninu (jiného) přirozeného čísla. Test, zda je dané číslo perfektní mocninou má ve výpočetní teorii čísel řadu aplikací: např. některé moderní prvočíselné testy, včetně slavného testu AKS, neumí rozlišit mezi prvočíslem a jeho mocninou, a proto je třeba na vstupu nejprve provést tento test. Naivní test, který počítá všechny možné odmocniny, má složitost (víceméně) kubickou. Pomocí několika triků lze srazit složitost na subkvadratickou (Bach-Sorenson) a s použitím rychlé aritmetiky dokonce na téměř lineární (Bernstein).
Cílem práce je nastudování a implementace těchto algoritmů a porovnání jejich reálné rychlosti. Implementace se předpokládá v jazyce C s použitím knihovny GMP. Kromě implementace by práce měla obsahovat i srovnání teoretické složitosti, a to s použitím klasické i rychlé aritmetiky. Možnost vlastního výzkumu na analogické téma: najít (rychlejší) test, který rozezná prvočíslo od netriviální mocniny prvočísla (což je vlastně ten speciální případ, který se objevuje např. v testech prvočíselnosti). |
| References |
| E. Bach, J. Sorenson. Sieve algorithms for perfect power testing. Algorithmica 9 (1993).
D. Bernstein. Detecting perfect powers in essentially linear time. Math. Comp. 67 (1998) . Cohen. A course in computational number theory, Springer. |