Je leest:

Nieuwe priemgetallentest ontdekt

Nieuwe priemgetallentest ontdekt

Auteur: | 6 september 2002

Het Indiase Institute of Technology (IIT) ontwikkelde een rekenmethode (algoritme) om in korte tijd te kunnen beslissen of een getal een priemgetal is of niet. Priemgetallen zijn gehele getallen met maar twee delers, zichzelf en één. Deel je een getal door zichzelf, krijg je de uitkomst één. Deel je een getal door één dan krijg je als uitkomst het getal zelf.

Een voorbeeld van een priemgetal is 19, het laatste priemgetal onder de twintig. Negentien is alleen deelbaar door 1 en 19 met een geheel getal als uitkomst. Priemgetallen zijn te gebruiken als sleutel bij de codering van geheime boodschappen, omdat het een uniek getal is. Een boodschap die versleuteld is met een priemgetal kan alleen met dat getal worden gedecodeerd.

Een toevallige andere sleutel (getal) zal nimmer werken, tenzij toevallig het priemgetal wordt gevonden. Maar die kans is klein, want er zijn vele duizenden priemgetallen met een lengte van miljoenen cijfers.

Van rechts naar links: Professor Manindra Agrawal en zijn twee studenten Neeraj Kayal en Nitin Saxena van het Indiase Institute of Technology (IIT). Zij ontwikkelden een algoritme om in korte tijd te beslissen of een getal een priemgetal is of niet.

Het grootste priemgetal dat tot februari 2002 bekend was, is een getal van ruim 4 miljoen (4053946) cijfers. Dit getal werd op 14 november 2001 ontdekt door Michael Cameron, George Woltman en Scott Kurowski. Hun computers deden er 42 dagen over om het getal te vinden.

Een Spartaanse methode om boodschappen te versleutelen. Een lange reeks letters onder elkaar betekenen niets zolang ze niet op de rol met het juiste formaat werden gewikkeld. Pas dan ontstonden leesbare zinnen. (copyrights Hrana Janto)

Het vinden van nieuwe priemgetallen duurt steeds langer omdat de getallen groter worden en de berekening steeds complexer. Maar nu hebben Indiase wetenschappers een oplossing gevonden. Professor Manindra Agrawal en zijn twee studenten Neeraj Kayal en Nitin Saxena van het Indiase Institute of Technology (IIT) hebben een algoritme ontwikkeld om in korte tijd te beslissen of een getal een priemgetal is of niet.

De Indiase wetenschappers hebben een antwoord op het probleem dat nooit met honderd procent zekerheid was te zeggen of een priemgetal – gevonden volgens algoritmen die al vijftien jaar in gebruik zijn – ook werkelijk een priemgetal was. De kans dat een getal van meer dan vier miljoen cijfers toch nog te delen is door een ander getal dan één of het getal zelf, is groot. De kans wordt ook groter naarmate het getal groter wordt.

Priemgetallen worden met een grote mate van toevalligheidgevonden. Als een priemgetal wordt gevonden, kan het fout zijn, maar met een kleine kans (Monte Carlo-algoritme), of er wordt zelden een priemgetal gevonden, maar als het er is, is het wel correct (Las Vegas-algoritme). Het nieuwe algoritme, gevonden door prof. Agrawal geeft een juist antwoord dat met een computer binnen redelijke tijd kan worden berekend.

Dit artikel is een publicatie van Marco van Kerkhoven.
© Marco van Kerkhoven, alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 06 september 2002

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.