|
|
Test Rabina-Millera a volba báze
Franců, Martin ; Simon, Petr (vedoucí práce) ; Čunát, Vladimír (oponent)
Práce se zabývá různými způsoby volby báze v Rabinově-Millerově testu. V teoretické části je učiněn krátký přehled prvočíselných testů podobných Rabinovu-Millerovu testu a je dokázáno několik tvrzení o struktuře množiny sil- ných lhářů v multiplikativní grupě. Vybrané netradiční volby báze jsou otestovány na množině lichých složených čísel od 100 do 200 000 000 a výsledky jsou porov- nány s výsledky při obvyklé volbě báze. Je vyslovena domněnka o vylepšení testu prostřednictvím používání bází určitého tvaru vzhledem k testovanému číslu. Sou- částí práce je také program, který implementuje posuzované způsoby volby báze. Tento program umožňuje uživateli pohodlné srovnávání výsledků testů s různými způsoby volby báze. V druhé části práce je dokumentace programu. 1 Seznam tabulek 2.1 Výsledky testů s různými volbami báze na testovací množině. . . . 19 2.2 Výsledky testů s různými volbami báze na spsp(2,3,5) < 101 2 z článku [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Typy zpráv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 Třídy hledačů bází. . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Názvy a funkce reportérů. . . . . . . . . . . . . . . . . . . . . . . 33 2 Seznam obrázků 2.1 Hustota lhářů v závislosti na poměru lháře ku testovanému...
|
|
|
Lucasův-Lehmerův test
Vejpustek, Ondřej ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
Cílem této práce je seznámit čtenáře s teorií kvadratických číselných těles a dokázat korektnost Lucasova-Lehmerova prvočíselného testu. Kvadratické číselné těleso je těleso tvaru Q( √ m). První kapitola popisuje základní vlastnosti okruhu celistvých čísel tohoto tělesa, důraz je kladen zejména na explicitní popis grupy jeho invertibilních prvků. Druhá kapitola studuje dělitelnost ideálů tohoto okruhu. Je dokázána věta o existenci a jedno- značnosti rozkladu každého ideálu na součin prvoideálů a věta charakterizující všechny prvoideály. Kapitola třetí využívá teorii kvadratických číselných těles k popisu a důkazu korektnosti Lucasova-Lehmerova prvočíselného testu - deterministického algoritmu ově- řujícího prvočíselnost čísel tvaru 2p − 1. 1
|
|
|
Test Rabina-Millera a volba báze
Franců, Martin ; Simon, Petr (vedoucí práce) ; Čunát, Vladimír (oponent)
Práce se zabývá různými způsoby volby báze v Rabinově-Millerově testu. V teoretické části je učiněn krátký přehled prvočíselných testů podobných Rabinovu-Millerovu testu a je dokázáno několik tvrzení o struktuře množiny sil- ných lhářů v multiplikativní grupě. Vybrané netradiční volby báze jsou otestovány na množině lichých složených čísel od 100 do 200 000 000 a výsledky jsou porov- nány s výsledky při obvyklé volbě báze. Je vyslovena domněnka o vylepšení testu prostřednictvím používání bází určitého tvaru vzhledem k testovanému číslu. Sou- částí práce je také program, který implementuje posuzované způsoby volby báze. Tento program umožňuje uživateli pohodlné srovnávání výsledků testů s různými způsoby volby báze. V druhé části práce je dokumentace programu. 1 Seznam tabulek 2.1 Výsledky testů s různými volbami báze na testovací množině. . . . 19 2.2 Výsledky testů s různými volbami báze na spsp(2,3,5) < 101 2 z článku [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Typy zpráv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 Třídy hledačů bází. . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Názvy a funkce reportérů. . . . . . . . . . . . . . . . . . . . . . . 33 2 Seznam obrázků 2.1 Hustota lhářů v závislosti na poměru lháře ku testovanému...
|
host ::
RSS.