On Generating Prime Numbers Efficiently

Thumbnail Image

Files

master_Sipilä_Juhani_2018.pdf (779.81 KB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
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

2018-06-19

Department

Major/Subject

Systems and Operations Research

Mcode

SCI3055

Degree programme

Master’s Programme in Mathematics and Operations Research

Language

en

Pages

56+4

Series

Abstract

The prime numbers can be considered as the building blocks of natural numbers, having innumerable applications in number theory and cryptography. There exist multiple different sieving algorithms for the generation of prime numbers. In this thesis, an elementary modular result is utilized to construct an analytically useful generator function and its inverse function. The functions are used to generate a (log)log-linear time complexity prime sieving algorithm which is further optimized to be of linear time complexity. The constructed algorithms and their operation are studied and the linear implementations in JS, Python and C++ are compared to other prime sieves.

Alkulukuja voidaan pitää luonnollisten lukujen rakennuspalikoina joilla on lukemattomia sovelluksia lukuteoriassa ja kryptografiassa. Alkulukujen luomiseen on olemassa useita erilaisia seulonta-algoritmeja. Tässä opinnäytetyössä käytetään modulaarista perustulosta analyyttisesti hyödyllisten kehitysfunktion ja sen käänteisfunktion luomiseen. Funktioiden avulla luodaan aikakompleksisuudeltaan (log)log-lineaarinen alkulukuseula, joka optimoidaan lineaariseksi. Rakennettuja algoritmeja ja niiden toimintaa tarkastellaan ja lineaarista implementaatiota JS, Python ja C++ ohjelmointikielillä verrataan toisiin alkulukuseuloihin.

Description

Supervisor

Ilmonen, Pauliina

Thesis advisor

Kaarnioja, Vesa

Keywords

prime number, prime sieve, algorithm, Myriad sieve

Other note

Citation

Permanent link to this item

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

Collections

[dipl] Perustieteiden korkeakoulu / SCI