Alkulukujen testauksesta

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-202111184066
Title: Alkulukujen testauksesta
Author: Hentunen, Johannes
Other contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
University of Helsinki, Faculty of Science
Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Publisher: Helsingin yliopisto
Date: 2021
Language: fin
URI: http://urn.fi/URN:NBN:fi:hulib-202111184066
http://hdl.handle.net/10138/336486
Thesis level: master's thesis
Degree program: Matematiikan, fysiikan ja kemian opettajan maisteriohjelma
Master 's Programme for Teachers of Mathematics, Physics and Chemistry
Magisterprogrammet för ämneslärare i matematik, fysik och kemi
Specialisation: Matematiikan opettaja
Teacher in Mathematics
Lärare i matematik
Abstract: 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.
Subject: Lukuteoria
alkuluvut
probabilistiset ja deterministiset alkulukutestit
Miller-Rabin
AKS


Files in this item

Total number of downloads: Loading...

Files Size Format View
Hentunen_Johannes_tutkielma_2021.pdf 520.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record