Priemgetallen  
       
 

PREVSitemapNEXT

 
       
    De moderne cryptografie maakt uitvoerig gebruik van het rekenen met gehele getallen én van het rekenen met priemgetallen.  In een vorige paragraaf zagen we hoe je tekst kan omzetten naar getallen, zodat we er vanaf nu altijd van uitgaan dat we getallen coderen.  Het klinkt dan wat vreemd om de boodschap “31415” naar iemand anders te verzenden, maar in werkelijkheid is dit getal gelijk aan een (ultra geheime) boodschap.

Er bleek al dat priemgetallen belangrijk zijn als je gehele getallen wilt delen door elkaar. Een priemgetal is een getal dat zelf alleen maar deelbaar is door 1 en door zichzelf.

 
   
 
Door de snelle evolutie van computers verandert de betekenis van wat een "groot" priemgetal is. Begin 2002 was het grootste bekende priemgetal het getal 213466917-1.  Dit getal heeft 4053946 cijfers.  Je kan op het internet mee zoeken naar nog grotere priemgetallen, bv. via www.primepages.org
  Om oeverloze discussies te vermijden, spreken we meteen af: “1” is géén priemgetal. Daar is een goede reden voor: als 1 geen priemgetal is, dan kunnen we elk ander getal op een unieke manier ontbinden in een product van priemgetallen. Als 1 wel een priemgetal is, dan is deze ontbinding in priemfactoren niet meer uniek, want dan kan je zeggen: 6=2*3 maar ook 6=1*2*3=1*1*2*3 ...

Een getal ontbinden in priemfactoren is niet altijd eenvoudig.  Zo kan je eenvoudig nakijken dat

1234567890987654321= 3*3*7*19*928163*1111211111,

maar hoe kan je weten dat 1111211111 zelf niet verder ontbonden kan worden? 

De enige manier om dit te weten te komen is door het getal te proberen delen door alle mogelijke priemgetallen, van 2 tot en met de vierkantswortel van dat getal.  Dus moet je al die priemgetallen kennen. En je kan ze alleen maar kennen door ze zelf weer te delen door alle priemgetallen van 2 tot de wortel van dat nieuwe getal, priemgetallen die je enkel kent door ze te delen door... 

 
   
 
    Voor hele grote getallen is dit zoveel werk dat men het als “onmogelijk” beschouwt.  En daarvan maken we gebruik: stel dat we een geheimschrift vinden dat je alleen maar kan ontcijferen door een heel groot (bijvoorbeeld meer dan 512 cijfers) geheel getal in priemgetallen te ontbinden. En stel dat dit onmogelijk is. Dan is het onmogelijk om dit geheimschrift te kraken.  In een volgende fiche geven we een eenvoudig voorbeeld van zulk geheimschrift.

 
   
 
   

Het programma "PriemGetal.exe" helpt je bij het berekenen van priemgetallen én bij het ontbinden van een groot getal in priemfactoren.  Door de beperking van het computergeheugen, beperken we ons tot getallen met maximaal 20 cijfers.  Je kan dit programma gebruiken om verderop de RSA-code te kraken.

 

 
   

Waarom moet je bij het zoeken van priemfactoren delen tot en met de wortel van het getal?

Leer de eerste 1000 priemgetallen van buiten.

 
       
   

 NEXT

 
       
       
    ---