QED

In het septembernummer van PC-Active gaat mijn Denkwerk-rubriek over het factoriseren van grote getallen. Aanleiding was de factorisatie van 2¹⁰³⁹ - 1 eind mei. Daar begint het artikel dan ook, maar ik bespreek ook vorige records, vooral van de RSA Factoring Challenge. Ik leg ook in grote lijnen de werking van de Rational Sieve uit om getallen te factoriseren. Dit algoritme is nog aan een algemeen geïnteresseerd publiek uit te leggen, omdat de wiskunde erachter heel wat eenvoudiger is dan bij de Special Number Field Sieve die voor het 1017 bits getal gebruikt werd. De algemene structuur van beide algoritmes is echter gelijkaardig.

Aan grote getallen factoriseren kleeft overigens al lang een Nederlands tintje. Enkele van de belangrijkste onderzoekers hiernaar zijn namelijk Nederlanders. In 1999 factoriseerde een team van het Amsterdamse CWI het getal RSA-155, een getal van 155 cijfers of 512 bits uit de RSA Factoring Challenge. Projectleider was Herman te Riele van het CWI, bijgestaan door een internationaal team, waaronder Arjen Lenstra, Peter Montgomery, Paul Leyland, Joel Marchand, Francois Morain en Paul Zimmermann. Het rekenwerk werd verdeeld onder ongeveer 300 computers over de hele wereld, waarvan 100 op het CWI stonden.

In het artikel wijs ik m’n lezers ook op een aantal projecten waar ze zelf aan kunnen deelnemen om grote getallen te factoriseren of nieuwe priemgetallen te vinden: NFSNet en GIMPS.