NRC Handelsblad 17-08-2002

Grote priemgetallen snel te vinden via Indiase methode

Een nieuwe methode om te testen of een getal een priemgetal is (een getal dat alleen deelbaar is door zichzelf of door ťťn) is wezenlijk sneller dan alle bestaande methoden. De methode van de Indiase wiskundigen Manindra Agrawal, Neeraj Kayal en Nitin Saxena van het Indian Institute of Technology in Kanpur test kandidaat-priemgetallen voor het eerst in `polynomiale tijd', wat inhoudt dat de rekentijd niet explosief toeneemt als het te testen getal groter wordt.

Priemgetallen spelen een centrale rol in de eeuwenoude tak van wiskunde die bekend staat als getaltheorie. Inmiddels worden ze onder andere gebruikt om informatie elektronisch te beveiligen met de RSA-versleutelingsmethode. Een snelle maar betrouwbare methode om getallen op de proef te stellen aangaande hun priemstatus is al eeuwen een heilige graal voor getaltheoreten.

Het eerste bekende rekenschema is de zeef van Eratosthenes van rond 240 voor Christus, en houdt in dat alle getallen tot en met het te testen getal achter elkaar opgeschreven worden. Vervolgens telt de tester van twee tot de wortel van het testgetal, om elke keer alle veelvouden van deze getallen op zijn papiertje weg te strepen.

Dit recept loopt echter in de papieren zogauw er er serieuze getallen getest gaan worden, zoals de priemgetallen met twintig cijfers in het RSA-algoritme. Bij ieder extra cijfer in het testgetal neemt de rekentijd met een vaste factor toe: een explosieve groei die computers al snel duizenden of miljoenen jaren rekentijd kost. De rekentijd neemt `exponentieel' toe met de grootte van het probleem, zeggen wiskundigen, die liever een `polynomiale' toename zien, waarbij de rekentijd op den duur evenredig is aan het kwadraat of een andere macht van het aantal cijfers in het testgetal.

De zoektocht naar die polynomiale priemtest is met de Indase methode eindelijk beŽindigd. OfficiŽle publicatie moet moet nog volgen, maar een wetenschappelijke beschrijving is al te lezen op de website www.cse.iitk.ac.in. Voor praktische toepassingen heeft de lange speurtocht naar priemgetal-testen eerder al methoden opgeleverd die snel en met zeer grote waarschijnlijkheid kunnen vaststellen of een getal priem is. Zulke, net niet helemaal waterdichte, methoden zijn in de praktijk veel sneller dan de nieuwe, waarvan de rekentijd ongeveer evenredig is aan de zesde macht van de lengte van het testgetal, oftewel: als het testgetal twee keer zo lang wordt moet er ongeveer 2(6e macht) (is 64) maal zo lang aan gerekend worden. Voor versleutelingstoepassingen zijn de oude tests dus nog handiger, maar de IndiŽrs hebben goede hoop dat ze hun methode nog sneller kunnen maken.

(c) Bruno van Wayenburg