Mersennen alkuluvut ja GIMPS-projekti

[ilkant]

Matematiikassa on käsite Mersennen alkuluku. Niitä lasketaan hajautetulla järjestelmällä, johon on luotu projekti GIMPS Projektin kotisivulta löytyy lisäohjeita.

Kuka tahansa voi osallistua kotitietokoneellaan projektiin. Kotisivulla Get Started opastetaan asentamaan tarvittava ohjelma tietokoneelle. Siitä on myös lähdekoodit saatavana. Voit ottaa yhden laskentaviipaleen tehtäväksi. Laskenta kuormittaa konetta tehokkaasti. Oma koneeni laski noin 10 tunnin ajon aikana 2,5 % tehtäväviipaleesta. Ohjelma toimii taustalla. Voit tehdä siinä samalla muutakin koneella. Ohjelmassa voi säätää parametreja, jolloin laskentatehokkuus voi nousta tai laskea ja koneen kuormitus sen mukaisesti.

Projektissa on mainittu jopa 3000 dollarin tai 50 000 dollarin palkintoja uusien alkulukujen löytäjälle. EFF on luvannut 100 000 dollarin palkinnon tietyt ehdot täyttävälle löydölle. Projektissa on Finland-tiimi, jossa on noin 50 jäsentä ja 208 tietokonetta. Voit liittyä siihenkin kotisivulla. Autat vielä matematiikan tiedettäkin pieneltä osin.

Mersennen luvuilla on useita lukuteoreettisia kuriositeettiominaisuuksia. Muun muassa parillisten täydellisten lukujen kuvaus perustuu niihin (parittomien täydellisten lukujen olemassaolo on avoin pulma). Lukua sanotaan täydelliseksi, jos se on aitojen tekijöidensä summa. Esimerkiksi 6 on täydellinen, koska sen tekijät ovat 1,2,3 ja 1+2+3=6. Jos 2^p-1 on alkuluku, niin n=2^(p-1)(2^p-1) on täydellinen (kun p=2, niin saadaan juurikin n=2). Tämä ja moni vastaava ominaisuus on mainittu Wikipedia-artikkelissa.

Yksi avoin ongelma on kysymys jatkuuko Mersennen torni? 2 on alkuluku, 2^2-1=3 on alkuluku, 2^3-1=7 on alkuluku, 2^7-1=127 on alkuluku, 2^127-1 on sekin alkuluku, ja se oli pitkään suurin tunnettu alkuluku. Tornin seuraava alkio 2^(2^127-1)-1 sitä vastoin on aivan liian suuri jopa GIMPSin käsiteltäväksi.

Mersennen tornin seurauksena saadaan vastaava torni polynomeja, jotka ovat jaottomia yli kahden alkion kunnan: x^2+x+1, x^3+x+1, x^7+x+1, x^127+x+1, x^(2^127-1)+x+1, joka sitten jatkuu tai ei. Käsittääkseni ainakin joku yrittää viritellä tuon 2^127 alkioisen kunnan päälle kryptografista konstruktiota. Mersenne ominaisuus nimittäin takaa, ettei tuon kunnan multiplikatiivisella ryhmällä ole pieniä aliryhmiä (joita hyökkääjä voisi hyödyntää). Tuo saattaa olla liian pieni nykyisissä systeemeissäs käytettäväksi.

(Viesti löytyy myös Tech GBBS foorumilta. En laittanut linkkiä sinne, jos joku haluaa kommentoida pysyen täällä)