Priempolynomen houden je bankrekening veilig

Wiskunde Hoe groter een getal, hoe kleiner de kans dat het een priemgetal is. Precies omgekeerd werkt het bij polynomen, zoals x4+2x3+1. Hoe langer zo’n polynoom, hoe groter de kans dat hij niet te ontbinden is. Die tegenstelling helpt bij de internetbeveiliging.

Illustratie Roland Blokhuizen

De parels onder de natuurlijke getallen zijn de priemgetallen, de gehele getallen die geen andere delers hebben dan 1 en zichzelf. Naarmate de getallen groter worden, worden de priemgetallen steeds zeldzamer. Zo zeldzaam, dat op de schaal van nul tot oneindig het percentage priemgetallen gelijk is aan nul. Dat mag onrealistisch klinken, want uitsterven doen de priemgetallen niet, maar het is volledig consistent met de strenge maar tricky logica van de statistiek.

Veel minder bekend dan de priemgetallen zijn de zogenoemde priempolynomen, en die zijn er juist in overvloed. Een voorbeeld van een polynoom is x2 + 4x + 3. Een van de dingen die middelbare scholieren uitentreuren moeten oefenen bij wiskunde, is het ontbinden van zulke polynomen in factoren. Dat betekent: schrijven als product van kleinere polynomen, of – voor dummies – ‘met haakjes schrijven’. Zo is het polynoom x2 + 4x + 3 te schrijven als (x + 1)(x + 3), het product van de polynomen x + 1 en x + 3.

Recent onderzoek

Zo’n ontbinding in factoren is niet altijd mogelijk. Het polynoom x2 + 2x – 1 kun je wel schrijven als (x + 1 – 2)(x + 1 + 2), maar zonder wortels lukt het niet. Net zoals 13 een priemgetal is omdat het niet te schrijven is als product van kleinere natuurlijke getallen, is x2 + 2x – 1 een priempolynoom omdat het niet te schrijven is als product van kleinere polynomen waarin, naast de variabele x, alleen gehele getallen voorkomen.

In een recent onderzoek bestudeerden Emmanuel Breuillard en Péter Varjú, een Franse en een Hongaarse wiskundige die beiden aan de universiteit van Cambridge zijn verbonden, zogeheten Newman-polynomen, vernoemd naar de Amerikaanse wiskundige Donald Newman (1930-2007). Een Newman-polynoom is een som van minstens twee termen; de eerste term is een zekere macht van x, bijvoorbeeld x5 of x19, de laatste term is 1. Daartussenin kunnen nog kleinere machten van x staan, maar dat hoeft niet. Voorbeelden van Newman-polynomen zijn x5 + 1, x3 + x2 + x + 1 en x19 + x4 + 1.

Het polynoom x5 + 1 is géén priempolynoom, omdat het te ontbinden is: (x + 1)(x4x3 + x2x + 1). Overigens is het polynoom tussen het tweede paar haakjes vanwege de mintekens geen Newman-polynoom. Ook x3 + x2 + x + 1 is niet priem: het is het product van x + 1 en x2 + 1. Maar x19 + x4 + 1 is wél priem.

Steeds spaarzamer

Wat hebben Breuillard en Varjú nu bewezen? Dat 100 procent van de Newman-polynomen priem is. Er zijn weliswaar oneindig veel Newman-polynomen die níét priem zijn, maar – net als de priemgetallen – komen ze steeds spaarzamer voor naarmate de exponenten van de polynomen groeien. Kennelijk vertonen de Newman-polynomen exact het tegengestelde gedrag van de natuurlijke getallen. Van de Newman-polynomen is 100 procent priem, van de natuurlijke getallen is het percentage priemen daarentegen nul.

Hun hoofdresultaat is zelfs nog sterker: de wiskundigen hebben aangetoond dat hetzelfde voor een nog veel ruimere klasse van polynomen geldt. Waarom benadrukken ze die Newman-polynomen dan zo? In een e-mail licht Breuillard toe: „Dat specifieke geval werd al in de jaren negentig vermoed door andere mensen.”

Markovketens

Aanvankelijk ging het onderzoek van Breuillard en Varjú helemaal niet over polynomen. Ze bestudeerden Markovketens, een onderwerp uit de kansrekening. Tot het begin van de twintigste eeuw waren munt- en dobbelsteenworpen belangrijke steunpilaren van dit vakgebied – situaties waarbij alle gebeurtenissen onafhankelijk van elkaar zijn. De Russische wiskundige Andrej Markov introduceerde ketens van ‘gelinkte’ gebeurtenissen: het toekomstige verloop van een of ander proces hangt af van de huidige toestand. Markovketens zijn tegenwoordig overal aanwezig. Het PageRank-algoritme van Google is bijvoorbeeld gebaseerd op een Markovketen.

Wiskundigen zijn vooral geïnteresseerd in het gedrag van een Markovketen ‘op den duur’. In de jaren tachtig werd een interessante eigenschap van Markovketens bewezen: op een zeker moment – het zogeheten ‘cut-off-moment’ – wordt, vrij plotseling, een evenwichtssituatie bereikt. Nog vlak vóór dat specifieke moment is de Markovketen nog ver van die evenwichtssituatie verwijderd.

Een voorbeeld: wat is het cut-off-moment bij het schudden van een pak kaarten? Dat betekent: hoe vaak moet je een pak van 52 kaarten schudden, met de bekende riffle shuffle, om ervoor te zorgen dat elke configuratie van de 52 kaarten even waarschijnlijk is? Het antwoord blijkt zeven keer te zijn: dan is de evenwichtssituatie bijna bereikt. Zes keer schudden is te weinig, vaker dan zeven keer schudden levert slechts kleine verbeteringen op (zie inzet). Er wordt gezegd dat de casino’s in Las Vegas hun regels aanpasten nadat wiskundigen dit in de jaren negentig hadden bewezen.

Breuillard en Varjú bestudeerden het cut-off-moment van ‘Markovketens op een eindig lichaam’. Lichamen zijn abstracte algebraïsche structuren met toepassingen in onder meer de coderingstheorie. „Op een gegeven moment realiseerden we ons dat onze methode zou werken als de meeste polynomen priem zijn”, schrijft Breuillard in zijn e-mail. Dat ze die eigenschap voor een grote groep polynomen konden bewijzen met technieken uit de theorie van Markovketens, is verrassend. Voor zover Breuillard en Varjú weten, is de link tussen Markovketens en priempolynomen nooit eerder gelegd. Het tweetal werkt nu aan een artikel over nieuwe resultaten in de theorie van Markovketens, gebruikmakend van hun nieuwe resultaat over polynomen.

Voor cryptografen is het bewijs van Breuillard en Varjú goed nieuws

Voor cryptografen is het bewijs van Breuillard en Varjú goed nieuws. In de moderne cryptografie spelen priemgetallen een wezenlijke rol. Veilig internetbankieren is mogelijk omdat het erg moeilijk is om grote getallen in priemfactoren te ontbinden. Het getal 2019 is het product van de priemgetallen 3 en 673. Zo’n viercijferig getal ontbindt een computer zó. Maar geef de computer een getal van een paar honderd cijfers en hij hapert. Dat komt doordat er geen efficiënt algoritme bestaat voor het ontbinden in priemfactoren. Juist het ontbreken van zo’n algoritme is de kracht van de moderne cryptografie. Een boodschap versleutelen is simpel (omdat het vermenigvuldigen van twee grote priemgetallen kinderspel is), ontsleutelen is daarentegen erg moeilijk (gegeven het product is het achterhalen van die twee priemgetallen praktisch ondoenlijk).

Een Newman-polynoom als neefje

Als de Newman-polynomen niet in groten getale priem waren geweest, was het decoderen in veel gevallen goed te doen geweest – en de cryptografie met behulp van priemgetallen dus onbruikbaar. Dat komt doordat elk natuurlijk getal een Newman-polynoom als neefje heeft. Is dat neefje geen priempolynoom, dan zijn de priemfactoren van het betreffende getal makkelijk te vinden. Dat zit zo. Om te bepalen wie het neefje van 287 is, schrijf je 287 in het tweetallig stelsel: 100011111 (kijk maar: 1 × 28 + 0 × 27 + 0 × 26 + 0 × 25 + 1 × 24 + 1 × 23 + 1 × 22 + 1 × 21 + 1 × 20 = 256 + 16 + 8 + 4 + 2 + 1 = 287). Het bijbehorende Newman-polynoom is x8 + x4 + x3 + x2 + x + 1 (vul voor x de waarde 2 in, en je krijgt 287). In tegenstelling tot voor grote getallen bestaat er voor Newman-polynomen met hoge exponenten wél een efficiënt ontbindingsalgoritme, mits zo’n ontbinding bestaat. In dit geval: x8 + x4 + x3 + x2 + x + 1 = (x2 + x + 1)(x6x5 + x3 + 1). Vul voor x het getal 2 in, et voilà: 287 = 7 × 41.

Doodlopende route

Voor het getal 287 is er dus een uitweg dankzij de Newman-polynomen. Maar probeer eens om via deze weg de priemfactoren van 301 te vinden. In het tweetallig stelsel is 301 gelijk aan 100101101, maar het bijbehorende Newman-polynoom, x8 + x5 + x3 + x2 + 1, is priem. Toch is 301 níét priem; het is het product van 7 en 43. Hoe groter de grootste exponent van een Newman-polynoom is, hoe groter de kans dat het polynoom priem is. Een kans die behoorlijk snel naar 100 procent convergeert, waardoor de route via Newman-polynomen om grote getallen in priemfactoren te ontbinden vrijwel altijd doodloopt.

Hoewel het resultaat van Breuillard en Varjú al 25 jaar geleden werd vermoed door de wiskundigen Andrew Odlyzko en Bjorn Poonen, is het voor cryptografen fijn dat er nu zekerheid is. Hoewel, zekerheid, er moet toch een slag om de arm gehouden worden. Want in hun bewijs veronderstellen Breuillard en Varjú de juistheid van de (gegeneraliseerde) Riemannhypothese. Dat is het grootste onopgeloste probleem in de wiskunde. Er is geen wiskundige die denkt dat de Riemannhypothese ónwaar is, maar een bewijs ontbreekt. De lijst is gigantisch van stellingen die beginnen met ‘als de Riemannhypothese waar is, dan …’. En aan die lijst hebben Breuillard en Varjú er nu dus weer één toegevoegd.

Lees over de Riemannhypothese: Hoe toevallig is de verdeling van priemgetallen?