aalto1 untyped-item.component.html
Methods for searching Mersenne primes
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Bachelor'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
Department
Major/Subject
Mcode
SCI3027
Degree programme
Language
en
Pages
30
Series
Abstract
Prime numbers, the integers greater than one that are only divisible by one and themselves, are an important subset of natural numbers. They are mathematically interesting due to the fundamental theorem or arithmetic: every positive integer can be uniquely written as a product of prime numbers. One of the most significant targets of prime number research is Mersenne numbers, i.e., integers of the form Mn = 2n - 1 where n is a positive integer. At the time of writing, 52 prime Mersenne numbers, or Mersenne primes, have been found, and the last 18 of them have been found by the Great Internet Mersenne Prime Search (GIMPS) project founded for searching these numbers.
This bachelor's thesis investigates the methods used by the GIMPS project for finding Mersenne primes. The goal is to provide an overview of these methods and the theory behind them. The thesis is a literature review that uses writings by GIMPS contributors, the source codes of the prime search software they use, and the mathematical literature behind the methods as sources. The methods examined in the thesis are trial factoring, Pollard's p - 1 method, Fermat probable prime test and the Lucas-Lehmer primality test.
The thesis concludes that although the general methods used for searching Mersenne primes have not changed since the introduction of the GIMPS project, multiple minor improvements developed in the last decade have accelerated the search process and improved its accuracy. The traditional Lucas-Lehmer primality test has been almost entirely replaced by the Fermat probable prime test equipped with Gerbicz error checking, which has significantly reduced the fraction of computation errors. Additionally, the Pietrzak verification method developed for the Fermat probable prime test has allowed the test results to be efficiently verified and has thus almost eliminated the need for replicating results on another computer.
Alkuluvut, eli yhtä suuremmat kokonaisluvut, jotka ovat jaollisia vain yhdellä ja itsellään, ovat merkittävä luonnollisten lukujen osajoukko. Niistä matemaattisesti kiinnostavan tekee aritmetiikan peruslause, eli se, että jokaisen positiivisen kokonaisluvun voi kirjoittaa yksikäsitteisesti alkulukujen tulona. Yksi tärkeimmistä alkulukututkimuksen kohteista on Mersennen luvut, eli kokonaisluvut muotoa Mn = 2n - 1, jossa n on positiivinen kokonaisluku. Alkulukumuotoisia Mersennen lukuja, eli Mersennen alkulukuja, on löydetty tähän mennessä 52 kappaletta, ja niistä 18 viimeistä on löytänyt niiden etsimiseen perustettu Great Internet Mersenne Prime Search (GIMPS) -projekti.
Tässä kandidaatintyössä perehdytään GIMPS-projektin käyttämiin menetelmiin Mersennen alkulukujen etsimiseen. Työn tavoitteena on antaa kokonaiskuva näistä menetelmistä ja tarjota yleiskatsaus niiden taustalla olevasta teoriasta. Työ on kirjallisuuskatsaus, joka käyttää lähdeaineistona GIMPS-jäsenten kirjoituksia, heidän käyttämiensä tietokoneohjelmien lähdekoodeja sekä menetelmien taustalla olevia tieteellisiä julkaisuja. Menetelmistä työssä käsitellään alkutekijöiden suoraa kokeilua (engl. trial factoring), Pollardin p - 1 -menetelmää, Fermat'n alkulukutestiä sekä Lucasin ja Lehmerin testiä.
Työn tuloksena havaitaan, että vaikka Mersennen alkulukujen etsimiseen käytettävät perusmenetelmät ovat pysyneet lähes muuttumattomina GIMPS-projektin alkuajoista, useat pienet parannukset ovat nopeuttaneet etsintäprosessia ja parantaneet sen tarkkuutta viimeisen kymmenen vuoden aikana. Perinteinen Lucasin ja Lehmerin alkulukutesti on korvattu lähes täysin Gerbiczin virheentunnistusmenetelmällä varustetulla Fermat'n alkulukutestillä, mikä on vähentänyt merkittävästi laskentavirheiden osuutta. Lisäksi Fermat'n alkulukutestille kehitetty Pietrzakin varmennusmenetelmä on mahdollistanut testin tulosten tehokkaan tarkistamisen ja tällä tavoin lähes poistanut tarpeen tulosten toistamiselle toisella tietokoneella.