WETENSCHAP - Mare 27, 8 april 2004
Proeftuin
De snelheid van een algoritme
‘Een wiskundige live in actie is iemand achter een bureau met een kladblok en een pen. Spannender wordt het niet.’ In het ‘lab’ van Reinier Bröker, aio algebraïsche getaltheorie, staat ook niets anders dan een bureau, een computer en een vrijwel lege boekenkast. Daar denkt hij na over het onderwerp van zijn onderzoek: de elliptische kromme.
Dat nadenken hem goed afgaat werd al duidelijk in vwo 5. Toen kwam hij tot de conclusie dat zijn wiskundeboek niet volledig was, met als gevolg dat het boek Getal en Ruimte nu de door hem verzonnen ‘Formule van Bröker’ kent.
Een elliptische kromme is een vergelijking met x en y, met x tot de derde macht en y in het kwadraat, bijvoorbeeld y² = x³ + 7x + 7. De variabelen x en y zijn onderdeel van een oneindig lichaam, ofwel een verzameling met oneindig veel getallen. Door bij berekeningen een eindig lichaam te gebruiken, een verzameling met een beperkt, gegeven aantal getallen, kun je uitrekenen hoeveel getallen daarvan voldoen aan de vergelijking. Maar dat is volgens Bröker geen uitdaging meer. ‘In 1985 is een oplossing gevonden om die berekening snel en gemakkelijk te maken.’
Het wordt pas interessant wanneer je de vraag omkeert. Het aantal oplossingen voor de vergelijking, ofwel het aantal punten op de elliptische kromme, wordt gegeven en daarmee bereken je welke kromme en welk eindig lichaam daar bijhoren. Tot nu toe kon niemand die berekening snel uitvoeren. Bröker heeft nu een algoritme geschreven waarmee het wel mogelijk is binnen beperkte tijd met een oplossing te komen. Die tijd varieert enorm, maar bij de invoer van het aantal 1030, het grootste getal dat hij tot nu toe heeft gebruikt, gaf zijn computer na 17 minuten de oplossing. ‘Dat is op zich vrij snel.’
De elliptische kromme is niet alleen wiskundig interessant, maar wordt sinds een jaar of twintig ook in de praktijk gebruikt om informatie te beveiligen. Dat gebeurt op dit moment al in mobiele telefoons en in de toekomst wellicht ook bij pincodes. Vooral daarom is het op dit moment een hot item in de algebra.
‘Mijn krommen zullen in praktijk waarschijnlijk niet worden gebruikt, omdat ze bijzondere eigenschappen hebben die niet relevant zijn voor bijvoorbeeld een aanbieder van mobiele telefoons. Dat is niet erg, de vraag of het mogelijk is een elliptische kromme te maken met bepaalde, mooie eigenschappen intrigeert me gewoon.’
Bröker is pas twee jaar met dit onderwerp bezig. ‘Het is geen onderdeel van de studie wiskunde. Toen ik hier als aio kwam, wist ik niet wat een elliptische kromme was. Er zijn maar weinig mensen die zich met deze discipline bezig houden, alleen in Parijs werkt iemand met ongeveer dezelfde vraag. Daar heb ik wel contact mee. We mailen over onze algoritmes en wie van ons sneller is.’
Nu zijn algoritme is geschreven en ook werkt, is Bröker vooral bezig met het uitbouwen en onderbouwen van zijn methode. ‘Dat is vooral een kwestie van nadenken en aantekeningen maken achter mijn bureau.’ Toch kreeg hij zijn beste idee ergens anders. ‘Ik dronk een kopje koffie met collega’s en dacht ineens: “Misschien moet het zo doen”. Dat is nu een jaar geleden en ik ben er nog steeds mee bezig.’
Christel Koop
