Onlangs werd er weer een groter priemgetal ontdekt; met meer dan 17 miljoen cijfers het grootst bekende priemgetal tot nu toe. Maar waarom doen mensen dat nou, zoeken naar die grote priemgetallen? En waarom zijn ze zo moeilijk te vinden?
Afgelopen week werd er een nieuw priemgetal gevonden. Priemgetallen zijn de getallen die alleen maar te delen zijn door zichzelf en door 1 en worden veel gebruikt in beveiligingssystemen. Hoe groter een priemgetal, hoe beter je beveiliging is. En het getal dat nu gevonden is, is zeker groot; het bestaat uit meer dan 17 miljoen cijfers. Wat een priemgetal is en wat je ermee kan, daar is al veel over gezegd (zie kader). Maar hoe is het getal eigenlijk ontdekt?
De laatste tijd worden alle priemgetallen door één groep ontdekt: GIMPS. Dit initiatief zoekt naar priemgetallen met behulp van distributed computing. Je kan je, als je dat wilt, opgeven als lid van GIMPS. Vervolgens installeer je een programmaatje op je computer en begint je pc automatisch met het ontdekken van priemgetallen.
Snel rekenen
Dit ontdekken van priemgetallen is nog niet eenvoudig. Omdat een priemgetal alleen door zichzelf en door 1 deelbaar is, zou je in principe moeten testen hoe ‘priemig’ een getal is, door te proberen het door elk getal tussen nul en zichzelf te delen. Dit kost echter ontzettend veel rekenkracht en dus tijd. Tijd die veel efficiënter te besteden is, want wiskundigen hebben de afgelopen eeuwen hard gewerkt om zo vloeiend mogelijk priemgetallen te vinden.
Om te beginnen hoef je de kandidaatpriem alleen maar te delen door andere priemgetallen. Het is immers niet nodig om een getal door 6 te delen als je al weet dat het getal niet door 2 te delen is. Dat komt omdat je 6 kan schrijven als 3 × 2, en elk getal dat deelbaar is door 6 ook deelbaar is door 3 en door 2 (probeer het maar eens voor een paar getallen die deelbaar zijn door zes). En eigenlijk hoef je ook niet met alle priemgetallen tot aan je kandidaatpriemgetal te delen; je hoeft zelfs maar tot de wortel van je priemgetal te delen. Deze twee trucjes schelen al veel tijd.
Stelling van Fermat
Het kan echter nóg sneller, dankzij de stelling van Fermat. Niet de beroemde Laatste stelling van Fermat, maar een andere. Deze stelling zegt dat als een getal p een priemgetal is, en een getal a is geen p-voud, a tot de macht p – 1 dan een p-voud plus 1 is (waarbij een p-voud betekent: een geheel aantal keer p). Zo opgeschreven lijkt dit ingewikkeld, maar in de praktijk valt het mee. We nemen bijvoorbeeld het getal 23 als (potentieel) priemgetal. Voor onze a kiezen we 3. Nu berekenen we 322 = 31381059609. Een groot getal, maar het blijkt dat (31381059609 – 1)/23 een geheel getal oplevert (en dat 31381059609 – 1 dus een 23-voud is. Dit betekent dat 23 priem is.
Eén groot probleem met de stelling van Fermat echter… Hij werkt niet. Zo blijkt de stelling voor het getal 341 te kloppen, maar 341 is deelbaar door 11! Gelukkig bleek later dat met een aantal kleine wijzigingen de stelling toch bruikbaar is. Dit werd ontdekt door de wiskundige Lucas en later verfijnd door Lehmer (in 1930). Het is deze Lucas-Lehmer-test die nu nog steeds gebruikt wordt, ook door GIMPS. Voor deze zoekmethode worden Mersenne-getallen gebruikt; dat zijn getallen van de vorm 2n – 1, en waarvan dankzij de Lucas-Lehmer-test relatief makkelijk vastgesteld kan worden of het priemgetallen zijn.
Checken van het priemgetal
Na lang rekenen van vele duizenden pc’s (GIMPS heeft inmiddels meer dan 100.000 gebruikers) werd op 6 februari 2013 dus (weer) een nieuw priemgetal gevonden. Het 48ste Mersenne-priemgetal, om precies te zijn. Tenminste, toen werd bevestigd dat het kandidaat-priemgetal echt priem was. Alle computers gaan samen controleren of een getal dat geslaagd is voor de Lucas-Lehmer-test écht een priemgetal is. Ondertussen wordt er aan een andere groep computers, die niets met de ene groep computers te maken heeft, hetzelfde gevraagd. Zo wordt het getal onafhankelijk op twee plekken gecheckt. Komt hetzelfde antwoord eruit, dan is het officieel; er is een nieuw priemgetal ontdekt.
Het feit dat GIMPS bijna al het rekenen, testen van Mersenne-getallen met de Lucas-Lehmer-test en verifiëren van priemgetallen aan haar gebruikers overlaat, betekent dat een centrale computer, die alles coördineert, eigenlijk maar weinig werk heeft. Zo kan er op een goedkope én snelle manier heel veel gedaan worden. Het is dan ook niet verrassend dat GIMPS zo veel nieuwe priemgetallen heeft gevonden in de afgelopen jaren.
Wiskundige & oud-kennislinkredacteur Ionica Smeets praat Pauw & Witteman bij over de bijzondere aard van de nieuwe priemontdekking.