Meno:Tomáš
Priezvisko:Váňa
Názov:Silné pseudoprvočísla
Vedúci:RNDr.Martin Mačaj, PhD.
Rok:2007
Kľúčové slová:pseudoprvočíslo, Riemannova hypotéza, Miller-Rabinov test, Fermatova veta
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.

Súbory bakalárskej práce:

pseudoprimes.pdf