Search results for "Lucas-Lehmer"

Alkulukutesteistä

2016

Tämän tutkielman tavoitteena on esittää tunnetuimmat alkulukutestit niin matemaattiselta perustoiltaan kuin käytännön toteutuksiltaan ohjelmakoodin muodossa. Alkulukutestit jaotellaan yleisesti deterministisiin ja probabilistisiin testeihin; deterministiset testit antavat täysin varman vastauksen, mutta ovat suurille luvuille huomattavasti probabilistia testejä hitaampia. Probabilistiset testit ovat nopeita tehdä, mutta saattavat antaa väärän vastauksen. Testien suoritusaikaa mitataan karkeasti niiden suorittamiseksi vaadittavien laskutoimitusten lukumääarällä. Tutkielmassa käsitellään deterministisistä testeistä jakolaskumenetelmä, Wilsonin lause, Prothin testi, Lucasin ja Lehmerin testi j…