Odkrito novo največje praštevilo

Kolaboracija GIMPS je odkrila novo največje praštevilo, ki ima kar 22,3 milijona mest v desetiškem zapisu oziroma pet milijonov več kot prejšnji rekorder. Praštevilo je odkril Curtis Cooper z Univerze Central Missouri, ki je imel v lasti tudi prejšnje tri rekorde. Univerza bo prejela 3000 dolarjev nagrade.

GIMPS je projekt distribuiranega izračunavanja, v katerem sodelujejo prostovoljci s celega sveta v iskanju novih največjih praštevil. Da je teh neskončno mnogo, je pokazal že Evklid, a iskanje čedalje večjih je zaradi omejene računske moči precej zahtevno. Splošen algoritem za preveritev, ali je neko število praštevilo, obstaja, a je popolnoma neuporaben za večja praštevila (celo klasično deljenje je hitrejše). Zato so zelo priljubljena Mersennova praštevila, katera lahko preverimo s sorazmerno nezahtevnim algoritmom. Če je 2ⁿ - 1 praštevilo, ga imenujemo Mersennovo praštevilo; trenutno jih poznamo 49. Preverjanje poteka tako, da izberemo naravni eksponent n in preverimo, ali je rezultat praštevilo. Odkritelji so torej predvsem srečni uganjevalci. Na klasičnem namiznem računalniku traja tak test približno mesec dni za števila z 20 milijoni mest.

Praštevila so uporabna v kriptografiji, a je novo odkrito praštevilo preveliko, da bi imelo praktično uporabno vrednost. Vseeno pa projekt GIMPS ni zgolj akademski, saj uporablja za testiranje stabilnosti in pravilnosti računalnikov po vsem svetu. Prav GIMPS je odigral ključno vlogo pri odkritju hrošča v procesorjih Skylake, o katerem smo pisali minuli teden.

Zanimivo je, da se je algoritem za preverjanje uspešno iztekel že 17. septembra lani, a tedaj zaradi hrošča program ni poslal elektronskega sporočila, ki bi koga opozoril na novo praštevilo. Kot datum odkritja bo veljal 7. januar 2016, ko je prvi človek dejansko izvedel, da poznamo novo praštevilo.