Record priemgetal gevonden dankzij internet en pentium

De Franse programmeur Joel Armengaud heeft op een standaard PC het tot nu toe grootste priemgetal gevonden, 420.921 cijfers lang (een pocket van 150 bladzijden) en behorend tot de Mersenne-catogerie. De 29-jarige Parijzenaar nam deel aan het GRIMPS-project, the GReat Internet Mersenne Prime Search.

Op initiatief van de Amerikaanse informaticus George Woltman zoeken sinds begin dit jaar 770 microprocessors over de hele wereld in hun vrije tijd in nauw onderling overleg naar priemgetallen. Tot nu toe was deze titanenarbeid voorbehouden aan Cray-supercomputers. Na ruim 60 uur rekenen slaagde Armengaud op een Pentium van 90 megahertz, de lichtste van de 18 computers die zijn softwarebedrijf GRIMPS ter beschikking had gesteld.

Priemgetallen zijn slechts deelbaar door één en door zichzelf. Voorbeelden zijn 7, 43 en 9191 maar er zijn er oneindig veel. Altijd is getaltheorie als het summum van zuivere wiskunde beschouwd - G.H. Hardy zei zich te zullen omdraaien in zijn graf mocht het alsnog tot toepassingen komen - maar sinds de jaren zeventig zijn priemgetallen verankerd in de cryptografie en mogen ze zich verheugen in de belangstelling van generaals en bankdirecteuren.

Mersenne-priemgetallen, genoemd naar een 17de-eeuwse Franse monnik met een fascinatie voor wiskunde, kunnen geschreven worden als 2-1. Inclusief die van Armengaud, Woltman et al. zijn er nu 35 bekend. Begin dit jaar kwam de Cray T94 van David Slowinski en Paul Gage, beiden werkzaam voor Silicon Graphics, met het vorige Mersenne-getal. Slowinski had het record, al dan niet gedeeld, sinds 1983 in bezit. Afgelopen week heeft zijn Cray na zes uur rekenen het priemgetal van Armengaud, te weten 2-1, in orde bevonden.

Het zoeken van Mersenne-priemgetallen gebeurt op basis van het Lucas-Lehmer algoritme, dat dateert van de jaren dertig. De centrale stelling luidt als volgt: voor oneven p is het Mersenne-getal 2-1 een priemgetal enkel en alleen als 2p-1 een deler (dus met rest 0) is van het getal S(p-1). Daarbij is S recursief gedefinieerd volgens S(n+1)=S(n)-2, met S(1)=4. Voor computers, die binair rekenen (met nullen en enen), is de Lucas-Lehmerprocedure zeer geschikt. Om die reden verwerkte Woltman het in een handzaam computerprogramma dat de GRIMPS-deelnemer via het internet kan downloaden. Op het world wide web staat aangegeven welke Mersenne-getallen inmiddels getest zijn en welke zijn uitgezet.

Met de vondst van het nieuwe Mersenne-priemgetal M1257787 ziet tegelijk een nieuw perfect getal het licht. Bij een perfect getal is de som van de delers gelijk aan het getal zelf, bijvoorbeeld 1+2+3=6. Hun oorsprong gaat terug tot de Griekse wiskundige Euclides. Tegenwoordig worden deze getallen vooral gebruikt om supercomputers te testen.

    • Dirk van Delft