Util Monster
Gratis
Priemtest · Ontbinding in factoren · Priemgetallen genereren
Een priemgetal is een natuurlijk getal groter dan 1 dat geen positieve delers heeft behalve 1 en zichzelf. Voorbeelden: 2, 3, 5, 7, 11, 13... Alle priemgetallen behalve 2 zijn oneven. Priemgetallen zijn de "atomen van de getallen."
Een oud algoritme ontwikkeld door de Griekse wiskundige Eratosthenes rond 240 v.Chr. Het vindt efficiënt alle priemgetallen tot n door herhaaldelijk veelvouden van elk priemgetal als samengesteld te markeren.
Tweelingpriemgetallen zijn paren priemgetallen die 2 van elkaar verschillen: (3,5), (5,7), (11,13), (17,19)... Of er oneindig veel tweelingpriemgetallen bestaan, blijft een onopgelost probleem.
• RSA-versleuteling: beveiliging op basis van de moeilijkheid van het ontbinden van grote getallen • Hashfuncties: hash-tabellen met priemgrootte verminderen botsingen • Willekeurige getallengeneratie: priemgetallen in PRNG-algoritmen • Natuur: levenscycli van cicaden gebruiken priemgetallen
Een priemgetal is een natuurlijk getal groter dan 1 met geen delers behalve 1 en zichzelf. Het kleinste priemgetal is 2, het enige even priemgetal. Reeks: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... De Griekse wiskundige Euclides bewees rond 300 v.Chr. dat er oneindig veel priemgetallen bestaan. Priemgetallen worden de "atomen van de getallen" genoemd omdat elk geheel getal > 1 uniek ontbindt in priemgetallen (Hoofdstelling van de rekenkunde). Voorbeelden: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
De eenvoudigste methode test deelbaarheid door alle getallen van 2 tot n-1, maar dat is inefficiënt. Een verbetering test alleen 2 tot √n, want als n = a × b, dan geldt a ≤ √n of b ≤ √n. Voor 101: √101 ≈ 10.05, dus test alleen 2, 3, 5, 7. De probabilistische Miller-Rabin-test behandelt zeer grote getallen efficiënt. AKS (2002) is het eerste deterministische algoritme met polynomiale tijd. Moderne cryptografie gebruikt honderden cijfers en vereist efficiënte tests.
Ontwikkeld door de Griekse wiskundige Eratosthenes rond 240 v.Chr. Proces: ① Noteer de getallen 2 tot n. ② Markeer 2 als priemgetal en schrap veelvouden (4,6,8,10...). ③ Het volgende ongemarkeerde getal 3 is priem, schrap veelvouden. ④ Ga verder met 5, 7, enz. tot √n. ⑤ De overblijvende getallen zijn priem. Voor n=30 zijn de priemgetallen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Tijdbestek: O(n log log n). Kan alle priemgetallen onder 1 miljoen in seconden vinden.
Priemfactorisatie drukt een getal uit als een product van priemgetallen. Volgens de hoofstelling heeft elk geheel getal > 1 een unieke ontbinding. Methode: ① Begin met het kleinste priemgetal 2. ② Deel herhaaldelijk door 2 tot dat niet langer kan. ③ Probeer daarna de volgende priemgetallen 3, 5, 7... ④ Ga door totdat het quotiënt 1 is. Voorbeeld 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Resultaat: 360 = 2³×3²×5. Toepassingen: berekening van ggd/kkg, vereenvoudigen van breuken, RSA-beveiliging.
Tweelingpriemgetallen verschillen 2 van elkaar: (3,5), (5,7), (11,13), (17,19), (29,31)... Het Tweelingpriemgetalvermoeden stelt dat er oneindig veel bestaan, maar is nog niet bewezen. In 2013 bewees Yitang Zhang dat oneindig veel priemparen hoogstens 70 miljoen verschillen; later werd dit teruggebracht tot 246. Het vermoeden van Goldbach (1742): elk even getal > 2 is de som van twee priemgetallen. Voorbeelden: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Gecontroleerd tot 4×10¹⁸, maar nog steeds onbewezen.
RSA-versleuteling, de kern van internetbeveiliging, vertrouwt op eenvoudige vermenigvuldiging maar moeilijke ontbinding van grote priemgetallen. Sleutelgeneratie: ① Kies grote priemgetallen p, q (elk 1024+ bits). ② Bereken n = p×q (publiek). ③ Bereken φ(n) = (p-1)(q-1). ④ Kies publieke exponent e die copriem is met φ(n) (meestal 65537). ⑤ Bereken private exponent d waarvoor e×d ≡ 1 (mod φ(n)). Publieke sleutel: (n,e), privésleutel: (n,d). Versleutelen: C = M^e mod n, ontsleutelen: M = C^d mod n. Het ontbinden van n om p,q te vinden zou de versleuteling breken, maar het ontbinden van honderden cijfers kost miljoenen jaren. Andere toepassingen: hash-tabellen met priemgroottes verminderen botsingen, 13/17-jarige cicadencycli vermijden overlap met roofdieren, priemritmes in muziek.