Testování perfektních mocnin

• Název práce v češtině: Testování perfektních mocnin
• Název v anglickém jazyce: Testing perfect powers
• Akademický rok vypsání: 2006/2007
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. RNDr. David Stanovský, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.10.2006
• Datum zadání: 30.10.2006
• Datum a čas obhajoby: 26.05.2008 00:00
• Datum odevzdání elektronické podoby: 26.05.2008
• Datum odevzdání tištěné podoby: 26.05.2008
• Datum proběhlé obhajoby: 26.05.2008
• Oponenti: doc. RNDr. Přemysl Jedlička, Ph.D.

Zásady pro vypracování

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).

Seznam odborné literatury

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.