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.
Zie ook:
- De Indiase priemgetalonderzoekers (Eng)
- Voor de liefhebber, het bewijs van de Indiërs
- De speurtocht naar priemgetallen
- Over het langste priemgetal tot nu toe
- Grote priemgetallen I (Eng)
- Over priemgetallen II (Eng)
- Hoe werkt de versleuteling met priemgetallen (Eng)
- Prijswinnen met het volgende priemgetal (Eng)
- Vraag Dr. Wiskunde (Eng)