Kokonaisluvun jakaminen tekijöihin ja Dixonin satunnaislukumenetelmä

Thumbnail Image

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-05-21

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

fi

Pages

18

Series

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.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Kaski, Petteri

Keywords

alkulukutekijät, tekijöihin jako, Dixonin algoritmi, satunnaisneliöinti

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202406114202

Collections

[kand] Perustieteiden korkeakoulu / SCI