Het ontbinden in priemfactoren

Prof.dr. Bas Edixhoven
Hoogleraar Wiskunde
Universiteit Leiden

1. Wat is de belangrijkste wetenschappelijke ontwikkeling in uw vakgebied?

In navolging van Hilbert, die in 1900 een lijst van 23 belangrijke open problemen in de wiskunde samenstelde, werd in 2000 een lijst van zeven problemen opgesteld, de zogenaamde Millenniumprijsproblemen.

Van deze zeven problemen is er inmiddels één opgelost: het vermoeden van Poincaré, door Perelman. De vraag wat de belangrijkste recente wetenschappelijke ontwikkeling in de wiskunde is, is dus niet moeilijk te beantwoorden: Perelmans bewijs van het vermoeden van Poincaré, ongeveer honderd jaar na de formulering ervan.

Informeel samengevat betekent dit vermoeden dat de gebruikelijke driedimensionale ruimte, zoals beschreven door Euclides en Descartes, topologisch (dat wil zeggen in de “rubbermeetkunde”) volledig gekarakteriseerd wordt door enkele eenvoudige intrinsieke eigenschappen. Een precieze beschrijving kan men op Wikipedia vinden. Een opmerkelijk feit is dat in alle andere dimensies het analoge probleem al opgelost was.

2. Op welke wetenschappelijke doorbraak hoopt u?

De hoop is natuurlijk dat er doorbraken zullen komen op het gebied van de overige zes Millenniumproblemen, bijvoorbeeld van het “P en NP” probleem, waarvan zowel het belang als de precieze betekenis voor iedereen te begrijpen is. Een vraag die dicht bij dit laatste probleem ligt betreft de complexiteit van het ontbinden van positieve gehele getallen (1, 2, 3, 4, etc.) in priemfactoren. Een geheel getal dat groter is dan 1 heet een priemgetal als het slechts twee delers heeft: 1 en zichzelf. Voorbeelden zijn 2, 3, 5, 7, 11, 13, maar ook 4407323881523619295230903290048715062902677684349609683641432547424336353342627705537660601159570849. Euclides bewees al dat er oneindig veel priemgetallen zijn. Ieder positief geheel getal kan worden ontbonden in een product van priemgetallen. Bijvoorbeeld: 4 = 2 x 2, 6 = 2 x 3, 9 = 3 x 3.

Een eenvoudige methode om te beslissen of een getal een priemgetal is of niet, is een computer programmeren om te kijken of het gegeven getal deelbaar is door 2, door 3 etc., en te stoppen als we een deler hebben gevonden of als we zien dat het gegeven getal een priemgetal is (als we zonder deler te vinden bij getallen groter dan de wortel van het getal in kwestie zijn aangekomen). Deze methode heeft een rekentijd die exponentieel groeit als functie van het aantal cijfers van het gegeven getal: als dat getal 100 cijfers heeft en een priemgetal is, dan moeten we toch minstens 10 tot de macht 50 delingen proberen. Ook al gebruikt men tienmiljard computers die tienmiljardn delingen per seconde doen, duurt dit nog steeds langer dan miljard keer miljard jaar.

De vraag is nu of het niet veel sneller kan.

Het volgende is bekend. Beslissen of een getal een priemgetal is kan worden gedaan in een rekentijd die hoogstens groeit als de zesde macht van het aantal cijfers.

Het antwoord op de vraag of ontbinden in priemfactoren gedaan kan worden in een rekentijd die hoogstens groeit als een vaste macht van het aantal cijfers is niet bekend. Een bewijs dat het niet zo snel kan zou het “P en NP” probleem oplossen. Op een kwantumcomputer kan het wel zo snel, maar het is niet bekend of kwantumcomputers kunnen bestaan.

De meest gebruikte versleutelmethode om vertrouwelijke gegevens over internet te sturen is gebaseerd op de aanname dat ontbinden in priemfactoren niet snel gedaan kan worden. Wie snel genoeg kan ontbinden kan alle berichten die zo versleuteld zijn ontcijferen.

3. Wat is de waarde van uw vakgebied voor de samenleving?

Het versleutelen van gegevens voor veilig dataverkeer over internet is één van de talloze voorbeelden van onmisbare wiskunde die verborgen is in hedendaagse techniek en apparaten. Andere voorbeelden zijn tomografie in de geneeskundige diagnostiek, kostenbesparende

optimalisaties in het spoorboekje van de NS, signaalverwerking en data-compressie voor beelden en geluid over internet. Wiskunde wordt ook wel eens de onzichtbare motor in de industrie genoemd.

Veel complexe fenomenen in onze wereld kunnen worden beschreven en verklaard met eenvoudige natuurwetten en modellen. Wiskundig onderzoek, bijvoorbeeld aan dit soort modellen, is meestal niet gericht op directe toepassingen, maar meer op het ontwikkelen van begrip. Het is juist deze drang naar algemener begrip die tot grote, en altijd onverwachte doorbraken leidt, die dan uiteindelijk weer hun toepassingen krijgen. Een voordracht van Gowers over het belang van de wiskunde is zeer aanbevolen.

Wiskundig opgeleiden zijn belangrijk in de samenleving vanwege hun vaardigheid problemen te analyseren, van welke soort dan ook, en oplossingen te vinden.

Ten slotte is wiskunde ook een vorm van kunst, zeker voor degenen die dit vak beoefenen. Zij genieten van de diepgang, verrassingen, eenvoud en elegantie in definities, stellingen en bewijzen. Het is aan de beoefenaars om nog meer hierover naar buiten te treden zodat een breder publiek hiervan kan meegenieten en er meer waardering voor kan opbrengen.


Andere bijdragen in Computer van de toekomst, Wiskunde, Wiskundige problemen