Kokonaisluvun jakaminen tekijöihin ja Dixonin satunnaislukumenetelmä

Abstract

Tutkielman aiheena on kokonaislukujen jakaminen tekijöihin ja erityisesti Dixonin satunnaisneliöintimenetelmän esitteleminen yhtenä tarkoituksenmukaisena välineenä. Työ on toteutettu kirjallisuuskatsauksena.

Johdantona varsinaiselle aiheelle tarkastellaan itse tekijöintiongelmaa ja sen lukuteoreettista taustaa. Tarkoituksena on esitellä riittävän kattavasti ongelman yksityiskohdat ja rajoitukset. Tekijöintiongelma on sinällään yksinkertainen esittää, mutta vaikeampi ratkaista riittävällä tehokkuudella. Yleisessä lukuteorian käsittelyssä keskitytään niihin asioihin, joilla on merkitystä tässä kandidaatintyössä esiteltävän tekijöintialgoritmin ymmärtämiseksi.

Pääasiana esitellään Dixonin satunnaisneliömenetelmä, joka on hallittu satunnaisalgoritmi yhdistetyn kokonaisluvun tekijöiden löytämiseksi. Satunnaisneliöalgoritmin toiminta käydään läpi sekä teoreettisesti että esimerkin avulla. Myös algoritmin oikeellisuuden todistus ja suoritusajan analysointi käydään läpi. Algoritmi ei aina anna vastausta sille esitettyyn ongelmaan, mutta asiat käydään läpi sillä ajatuksella, että se antaisi halutun vastauksen riittävän usein.

Yhteenvetoa esitellään vielä muita erilaisia tekijöintialgoritmeja ja vertaillaan niitä Dixonin satunnaisneliömenetelmään ja toisiinsa.