Priemgetallen
14 Jan 2007
Niets is zo eenvoudig als de getallen 1, 2, 3, 4, ..., ook wel de natuurlijke getallen genoemd. Deze getallen hebben allerlei bijzondere eigenschappen. Eén hiervan is de ontbinding in priemfactoren. Op deze pagina leggen we uit wat dat is. Ook vertellen we iets over hoe priemgetallen gebruikt kunnen worden om allerlei dingen, bijvoorbeeld jouw pinpas, te beveiligen.
Sommige getallen kun je schrijven als het product van twee andere getallen, bijvoorbeeld 10 = 2 × 5 en 16 = 4 × 4. Maar dat kan niet bij alle getallen. Het getal 7 bijvoorbeeld kun je alleen op een flauwe manier zo schrijven: 7 = 1 × 7. Het kan niet op een andere manier, omdat 7 niet deelbaar is door andere getallen dan 1 en 7. We noemen 7 daarom een priemgetal. Priemgetallen zijn getallen die alleen deelbaar zijn door 1 en door zichzelf.
Wiskundigen hebben afgesproken dat het getal 1 geen priemgetal is. Wel priemgetallen zijn bijvoorbeeld 2, 3, 5, 7, 11, 13, 17, 19, 23, ... We zeggen ook wel: "Het getal 11 is priem" in plaats van "Het getal 11 is een priemgetal."
Welke van de getallen 57, 58 en 59 is een priemgetal?
Je antwoord:
Je antwoord is juist!Helaas, je antwoord is niet juist.Het juiste antwoord is: 59
Elk getal dat geen priemgetal is, kun je schrijven als product van twee kleinere getallen. Als die kleinere getallen ook geen priemgetallen zijn, kun je die ook weer schrijven als een product van andere getallen. Zo kun je doorgaan totdat je alleen maar priemgetallen over hebt.
Neem bijvoorbeeld het getal 180. We kunnen dit schrijven als 180 = 9 × 20. Maar 9 is geen priemgetal en kunnen we schrijven als 9 = 3 × 3. Dus we kunnen 180 ook schrijven als 180 = 3 × 3 × 20. Omdat 3 een priemgetal is, kunnen we daar verder niets mee. Maar 20 is geen priemgetal: 20 = 2 × 10. Dus we krijgen 180 = 3 × 3 × 2 × 10. Het getal 10 is nog steeds niet priem, dus we kunnen dat ook weer als een product schrijven: 10 = 2 × 5. Dus 180 = 3 × 3 × 2 × 2 × 5. Alle getallen in dit product zijn priemgetallen, dus nu kunnen we niet meer verder.
Een getal schrijven als het product van allemaal priemgetallen heet het ontbinden van het getal. De ontbinding van 180 is 3 × 3 × 2 × 2 × 5. In deze ontbinding komen drie verschillende priemgetallen voor: 3, 2 en 5. Dit heten ook wel de priemfactoren van 180. Je ziet dat een priemfactor meer dan één keer in de ontbinding van een getal voor kan komen.
Welke van de volgende ontbindingen is niet goed?
a. 77 = 7 × 11
b. 100 = 5 × 5 × 2 × 2
c. 99 = 9 × 11
Je antwoord:
Je antwoord is juist!Helaas, je antwoord is niet juist.Het juiste antwoord is: 0
Cryptografie met grote priemgetallen
Wiskunde wordt veel gebruikt voor de beveiliging van allerlei dingen. Mensen willen vaak berichten naar elkaar sturen die niet door iemand anders gelezen kunnen worden. Dit komt bijvoorbeeld voor in het leger, maar ook als jij in een winkel betaalt met jouw pinpas. Je pincode wordt vanuit de winkel naar de bank gestuurd, die controleert of de pincode klopt. Het is natuurlijk niet de bedoeling dat iemand zomaar dat bericht kan onderscheppen en dan achter jouw pincode komt. Het bericht wordt daarom goed beveiligd met behulp van een speciale tak van wiskunde die cryptografie heet.
Je pincode wordt beveiligd met cryptografie.
Er zijn allerlei methodes om berichten te beveiligen en een van de meest populaire gebruikt priemgetallen. Deze methode heet RSA. Het idee achter RSA is dat het heel makkelijk is om twee grote getallen met elkaar te vermenigvuldigen, maar heel moeilijk om van een heel groot getal de ontbinding in priemgetallen te bepalen.
Als ik jou vraag om het getal 227 × 251 uit te rekenen, dan heb jij dat waarschijnlijk zo gedaan, op papier of met een rekenmachientje. Binnen de kortste keren weet je mij te vertellen dat het antwoord 56977 is. Maar kun je mij ook de ontbinding in priemgetallen van het getal 47477 vertellen? Zelfs met een rekenmachientje kom je daar waarschijnlijk niet zo snel uit.
Om RSA te gebruiken, heb je twee heel grote priemgetallen nodig. Alleen de ontvanger van het bericht (in het geval van de pinpasbetaling is dat de bank) kent deze twee priemgetallen. Alle andere mensen kennen het product van de twee priemgetallen, maar niet de priemgetallen zelf. De verzender van het bericht (bijvoorbeeld de pinautomaat in de winkel) heeft dat product nodig om het bericht te beveiligen. Als het eenmaal beveiligd is, kun je het alleen nog lezen als je de twee priemgetallen kent waaruit het product is opgebouwd. Het is ontzettend moeilijk om zo'n groot product te ontbinden, dus niemand kan die priemgetallen zelf vinden. De enige die het bericht kan lezen is dus degene die de priemgetallen al had, in ons voorbeeld de bank.
Auteur: Birgit van Dalen