Alkulukujen testauksesta

Lukuteoria tutkii kokonaislukujen ominaisuuksia, kuten jaollisuutta. Sekä kiinnostavaa että käytän-nöllistä on löytää keinoja selvittää onko jokin kokonaisluku jaettavissa millään toisella kokonais-luvulla. Näitä keinoja tai algoritmeja kutsutaan alkulukutesteiksi ja ne esiintyvät merkittävässäroolissa nykyaikaisessa tietoturvassa ja salaamisessa.Tässä työssä esitellään alkeellisia alkulukutestejä kuten Eratostheneen seula, Wilsonin lause ja Fer-mat’n testi, sekä suurten alkulukujen testaamiseen käytettyjä tehokkaampia menetelmiä. Alkulu-kutestit jaotellaan deterministisiin sekä probabilistisiin testeihin sen mukaan, antavatko ne var-man oikean tuloksen vai jollain tunnetulla todennäköisyydellä epävarman tuloksen. Epävarmempiprobabilistinen testi on kuitenkin determinististä käytännölisempi, sillä se voidaan ajaa riittävänmonta kertaa luotettavan tuloksen saamiseksi ja silti suoriutua determinististä testiä nopeammin.Erityisesti työssä keskitytään Miller-Rabinin probabilistiseen eli satunnaistettuun alkulukutestiin,joka on algoritmina nopea eli tehokas suuria lukuja testatessa. Työssä esitellään myös ensimmäi-nen polynomisessa ajassa suoriutuva deterministinen alkulukutesti AKS, jonka suoritumisaika elilaskutoimitusten lukumäärä on polynominen testattavan luvun numeroiden määrän suhteen.Työssä käydään läpi lukuteoreettista taustaa siinä määrin, kuin on alkulukutestien ymmärtämi-sen osalta oleellista, sekä katsastetaan myös lukuteorian sisältöjä ja opetusta lukiossa. Oleellinentaustateoria sisältää muun muassa kogruenssin, kiinalaisen jäännöslauseen, sekä Fermat’n pienenlauseen. Työssä esitellään myös Mersenneen alkuluvut ja näihin liittyvä yksinkertainen ja tehokasLucas-Lehmerin deterministinen alkulukutesti.Lukuteoriaa opetetaan vain vähän tai ei laisinkaan perusopetuksessa niin Suomessa kuin maail-mallakin. Lukion valinnainen kurssi Algoritmit ja lukuteoria antaa riittävät valmiudet tutustua it-senäisesti alkulukutesteihin tarvittavaan pohjateoriaan, kuten Fermat’n pieneen lauseeseen, muttakurssin varsinaiseen sisältöön alkulukujen testaus ei kuulu alkeellisimpia menetelmiä lukuunotta-matta.Lukuteoreettisten ongelmien pohtiminen ja lukuteorian käsitteiden opiskelu edistää opiskelijoidensuhtautumista matematiikkaan, vaikuttaa positiivisesti näiden metakogniitiivisiin kykyihin, sekäedistää ongelmanratkaisun ja todistamisen taitoja