| Abstrakt: | Práca sa zaoberá metódami testovania prvočíselnosti, konkrétne predovšetkým myšlienkovou líniou založenou na dôsledkoch Malej Fermatovej vety. Opisuje pojem pseudoprvočísel ako prekážky efektívneho využitia algoritmov
a zaoberá sa ich existenciou a relatívnou početnosťou v množine prirodzených čísel. Podáva prehľad metód, ktoré postupne zlepšujú pravdepodobnosť úspechu a všetky sú z hľadiska výpočtovej zložitosti polynomiálne od veľkosti vstupu. Takisto sa zaoberá Riemannovou hypotézou a jej dôsledkami, ktoré priamo súvisia s Miller-Rabinovym prvočíselným testom a umožnujú upraviť ho do deterministickej podoby. Práca je predovšetkým prehľadom teoretického pozadia metód a nezaoberá sa do podrobností praktickými aplikáciami ani otázkami výpočtovej zložitosti. Mala by však poskytovať ucelený pohľad na teoretické pozadie nutné pri skúmaní testov z hľadiska matematickej korektnosti a pravdepodobnosti ich omylu v nedeterministickej podobe.
|
|---|