Prime Numbers.pdf

# Priemgetallen en hun distributie Dit gedeelte biedt een gedetailleerd overzicht van priemgetallen, de fundamentele stelling van de rekenkunde en de distributie van priemgetallen naarmate getallen groter worden, met inbegrip van de rol van de natuurlijke logaritme. ### 1.1 Definitie van priemgetallen Een geheel getal $p > 1$ is een priemgetal als en slechts als zijn enige delers $\pm 1$ en $\pm p$ zijn. Priemgetallen zijn fundamenteel in de getaltheorie en spelen een cruciale rol in diverse wiskundige technieken [2](#page=2). ### 1.2 De fundamentele stelling van de rekenkunde De fundamentele stelling van de rekenkunde stelt dat elk geheel getal $a > 1$ op een unieke manier kan worden ontbonden in een product van priemfactoren. Deze unieke ontbinding kan worden uitgedrukt als [2](#page=2): $$a = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_t^{a_t}$$ waarbij $p_1 < p_2 < \ldots < p_t$ priemgetallen zijn en elke $a_i$ een positief geheel getal is. Dit betekent dat een getal slechts op één specifieke manier als een product van priemfactoren kan worden geschreven [2](#page=2). > **Voorbeeld:** Het getal 60 kan op slechts één manier worden ontbonden in priemfactoren: $2 \cdot 2 \cdot 3 \cdot 5$ [2](#page=2). ### 1.3 De distributie van priemgetallen #### 1.3.1 De frequentie van priemgetallen Er bestaat een natuurlijke vraag of het aantal priemgetallen eindig is en of de kans om een priemgetal te vinden kleiner wordt naarmate de getallen groter worden. Het blijkt dat de gemiddelde afstand tussen twee priemgetallen in de buurt van $n$ gelijk is aan de natuurlijke logaritme van $n$, aangeduid als $\ln(n)$. Dit houdt in dat men gemiddeld $\ln(n)$ getallen zou moeten testen om een priemgetal te vinden in de orde van grootte van $n$. Omdat even getallen (behalve 2) geen priemgetallen kunnen zijn, kan men stellen dat men gemiddeld $0.5 \cdot \ln(n)$ getallen zou moeten testen [3](#page=3). #### 1.3.2 De natuurlijke logaritme De natuurlijke logaritme ($\ln$) is de exponent waartoe het getal $e$ (ongeveer 2.71) verhoogd moet worden om de input van de functie te verkrijgen. Ter vergelijking, de logaritme met basis 10, genoteerd als $\log$, vereist dat 10 tot een bepaalde macht wordt verheven om de input te verkrijgen [3](#page=3). > **Voorbeeld:** > * $\ln \approx 2.07$, omdat $e^{2.07} \approx 8$ [3](#page=3) . > * $\log = 2$, omdat $10^2 = 100$ [3](#page=3). > * $\ln \approx 4.6$, omdat $e^{4.6} \approx 100$ [3](#page=3). Voor dit onderwerp is het relevant om te weten dat $\ln \approx 0.69$ en dat de logaritmische eigenschap $\ln(a^b) = b \cdot \ln(a)$ van toepassing is [2](#page=2) [4](#page=4). #### 1.3.3 Schatting van het aantal priemgetallen Met behulp van de natuurlijke logaritme kunnen schattingen worden gemaakt van het aantal priemgetallen in specifieke intervallen. Voor RSA 2048, een cryptografisch algoritme dat veel gebruik maakt van grote priemgetallen, wordt het interval tussen $2^{1023}$ en $2^{1024}$ beschouwd. De afstand tussen priemgetallen in dit bereik wordt geschat op $\ln(2^{1024}) = 1024 \cdot \ln \approx 1024 \cdot 0.69 = 707.2$. Dit betekent dat men gemiddeld slechts ongeveer $707.2 / 2 \approx 354$ getallen hoeft te testen om een priemgetal te vinden. Het geschatte aantal priemgetallen in dit specifieke bereik is $2^{1023} / 707.2 \approx 1.4 \cdot 2^{1013}$, wat een zeer groot aantal is [2](#page=2) [4](#page=4). > **Conclusie:** De intuïtieve gedachte dat priemgetallen schaarser worden naarmate getallen groter worden, is correct. Echter, de kans om een priemgetal te vinden in relevante intervallen blijft relatief hoog, vooral gezien de efficiëntie van de tests om de primaliteit van een getal te bepalen [4](#page=4). De grafiek van $n / \ln(n)$ tegen $n$ toont een lineair verband, wat aangeeft dat het aantal priemgetallen onder een gegeven getal $n$ zich ontwikkelt volgens de ratio $1/\ln(n)$. Dit impliceert dat er gemiddeld één priemgetal is in elke reeks van $\ln(n)$ getallen [4](#page=4). --- # Stelling van Fermat en Euler Dit gedeelte behandelt de Stelling van Fermat en de Euler-functies, met specifieke aandacht voor de totientfunctie en de Stelling van Euler als een generalisatie van de Stelling van Fermat, inclusief hun toepassingen. ### 2.1 De Stelling van Fermat De Stelling van Fermat, ook wel bekend als de Kleine Stelling van Fermat, is een fundamentele stelling in de getaltheorie met belangrijke toepassingen, met name in de cryptografie. #### 2.1.1 Basisformulering en implicaties De stelling stelt dat indien $p$ een priemgetal is en $a$ een positief geheel getal dat niet deelbaar is door $p$, geldt dat $a^{p-1} \equiv 1 \pmod{p}$ [5](#page=5). Een alternatieve, maar even nuttige vorm van de stelling luidt: als $p$ een priemgetal is en $a$ een positief geheel getal, dan geldt $a^p \equiv a \pmod{p}$ [5](#page=5). > **Tip:** Beide formuleringen zijn essentieel om te onthouden, aangezien ze verschillend in toepassingen kunnen zijn, vooral bij het berekenen van modulaire rekenkunde. De Stelling van Fermat biedt ook een efficiënte methode voor het berekenen van de multiplicatieve inverse modulo $p$. Specifiek, voor $a^{p-1} \equiv 1 \pmod{p}$, kan $a^{-1} \equiv a^{p-2} \pmod{p}$ worden afgeleid. Dit is cruciaal voor snelheidsoptimalisaties in algoritmen zoals RSA, met name bij het gebruik van de Chinese Reststelling (CRT) [5](#page=5). ### 2.2 De Euler-functies (phi-functie) De Euler-functie, ook wel de phi-functie ($\phi(n)$) genoemd, is een belangrijke functie in de getaltheorie die het aantal positieve gehele getallen kleiner dan of gelijk aan $n$ telt die relatief priem zijn met $n$. Twee getallen zijn relatief priem als hun grootste gemene deler (GCD) gelijk is aan 1 [6](#page=6). #### 2.2.1 Definitie en berekening Het concept van de phi-functie kan geïllustreerd worden door het aantal getallen te tellen die geen gemeenschappelijke delers hebben met een gegeven getal $n$. Bijvoorbeeld, voor $n=48$, zouden we alle getallen van 1 tot 47 controleren en degenen verwijderen die een gemeenschappelijke deler hebben met 48 (zoals 2, 3, 4, enz.). Het aantal resterende getallen is $\phi $. Omdat $48 = 2^4 \times 3$, hoeven we alleen de delers 2 en 3 te overwegen. De uitkomst is 16 [6](#page=6). Voor een priemgetal $p$ geldt dat alle getallen van 1 tot $p-1$ relatief priem zijn met $p$. Daarom is $\phi(p) = p-1$ [6](#page=6). Voor een getal van de vorm $n = p \times q$, waarbij $p$ en $q$ verschillende priemgetallen zijn, kunnen we de volgende logica toepassen: het totale aantal getallen van 1 tot $pq-1$ is $pq-1$. We verwijderen vervolgens alle veelvouden van $p$ (dit zijn $q-1$ getallen) en alle veelvouden van $q$ (dit zijn $p-1$ getallen). Dit leidt tot de formule $\phi(pq) = (pq - 1) - (p-1) - (q-1) = pq - p - q + 1 = (p-1)(q-1)$. Deze regel geldt alleen als $p$ en $q$ de enige priemfactoren zijn en geen gemeenschappelijke delers hebben [6](#page=6) [7](#page=7). De notatie voor de Euler-totientfunctie kan variëren, met de Griekse letters phi als $\phi$, $\phi$, of $\varphi$ [7](#page=7). Enkele belangrijke eigenschappen van de phi-functie zijn: * Voor een priemgetal $p$: $\phi(p) = p-1$ [8](#page=8). * Voor twee verschillende priemgetallen $p$ en $q$: $\phi(pq) = (p-1)(q-1)$ [8](#page=8). * Voor een macht van een priemgetal $p^n$: $\phi(p^n) = p^n - p^{n-1}$ [8](#page=8). * Als $m$ en $n$ relatief priem zijn (d.w.z., $\text{gcd}(m,n)=1$), dan geldt de multiplicativiteit: $\phi(mn) = \phi(m)\phi(n)$ [8](#page=8). **Voorbeeld berekening van $\phi(n)$:** Om $\phi $ te berekenen, ontbinden we 600 in priemfactoren: $600 = 2^3 \times 3 \times 5^2$ . Met behulp van de eigenschappen: $\phi = \phi(2^3 \times 3 \times 5^2)$ . Aangezien $2^3$, $3$, en $5^2$ relatief priem zijn, kunnen we de multiplicativiteit gebruiken: $\phi = \phi(2^3) \times \phi \times \phi(5^2)$ [3](#page=3) . $\phi = (2^3 - 2^{3-1}) \times (3-1) \times (5^2 - 5^{2-1})$ . $\phi = (8 - 4) \times \times (25 - 5)$ [2](#page=2) . $\phi = 4 \times 2 \times 20$ . $\phi = 160$ [8](#page=8). > **Tip:** Het maximaal mogelijke resultaat voor $\phi(n)$ is $n-1$, wat optreedt wanneer $n$ een priemgetal is. De waarden van $\phi(n)$ voor veel even getallen liggen ongeveer op de lijn $y = x/2$. ### 2.3 De Stelling van Euler De Stelling van Euler is een krachtige generalisatie van de Kleine Stelling van Fermat. Waar Fermat's stelling geldt voor een priem modulues $p$, geldt de Stelling van Euler voor elk positief geheel getal $n$. #### 2.3.1 Formulering en toepassingen De Stelling van Euler stelt dat voor elk paar van positieve gehele getallen $a$ en $n$ die relatief priem zijn (d.w.z., $\text{gcd}(a,n)=1$), geldt: $a^{\phi(n)} \equiv 1 \pmod{n}$ [9](#page=9). Dit resultaat is direct gerelateerd aan de Stelling van Fermat, aangezien voor een priemgetal $p$, $\phi(p) = p-1$. Als we dit substitueren in de Stelling van Euler, krijgen we $a^{p-1} \equiv 1 \pmod{p}$, wat precies de Kleine Stelling van Fermat is [9](#page=9). Net als bij de Stelling van Fermat, is er een alternatieve vorm van de Stelling van Euler die nuttig kan zijn, zelfs als $a$ en $n$ niet relatief priem zijn. Deze vorm wordt soms afgeleid uit de eerdere stelling en wordt gebruikt in cryptografische contexten, met name in RSA. De alternatieve vorm is [9](#page=9): $a^{\phi(n)+1} \equiv a \pmod{n}$ [9](#page=9). Het is opmerkelijk dat de vergelijking $a^x \equiv a \pmod{n}$ wordt voldaan voor verschillende waarden van $x$, waaronder $x = 1$, $\phi(n)+1$, $2\phi(n)+1$, $3\phi(n)+1$, enzovoort. Dit kan worden uitgedrukt als $x \equiv 1 \pmod{\phi(n)}$. Deze relatie vormt de basis voor het RSA-cryptosysteem [10](#page=10) [9](#page=9). Door de tweede vergelijking te vermenigvuldigen met $a^{\phi(n)}$, krijgen we ook dat $a^{\phi(n)+1} \equiv a \pmod{n}$. Door dit te herhalen, vinden we dat $a^{k\phi(n)+1} \equiv a \pmod{n}$ voor elk positief geheel getal $k$. Dit geeft de reeks oplossingen voor $x$ die hierboven zijn genoemd [10](#page=10). --- # Miller-Rabin algoritme voor primaliteitstesten Dit onderdeel introduceert het Miller-Rabin algoritme als een probabilistische methode om de primaliteit van een getal te testen, gebaseerd op de stelling van Fermat [11](#page=11). ### 3.1 De basis van het Miller-Rabin algoritme Het Miller-Rabin algoritme is een probabilistische methode voor het testen van de primaliteit van een getal. Het algoritme is gebaseerd op de stelling van Fermat, die stelt dat als een getal $n$ een priemgetal is, dan geldt $a^{n-1} \equiv 1 \pmod{n}$ voor elke integer $a$ met $1 < a < n-1$. Het Miller-Rabin algoritme controleert deze stelling voor een aantal willekeurig gekozen waarden van $a$ [11](#page=11). #### 3.1.1 Werkingsprincipe Het kernidee van Miller-Rabin is om de kandidaat-priemgetal $n$ (een oneven getal) te schrijven als $n-1 = 2^k \cdot q$, waarbij $k > 0$ en $q$ een oneven getal is. Vervolgens wordt een willekeurige integer $a$ gekozen met $1 < a < n-1$. Het algoritme doorloopt de volgende stappen [11](#page=11): 1. **Vind $k$ en $q$**: Schrijf $n-1$ als $2^k \cdot q$ met $k > 0$ en $q$ oneven [11](#page=11). 2. **Kies willekeurige $a$**: Selecteer een willekeurige integer $a$ zodanig dat $1 < a < n-1$ [11](#page=11). 3. **Eerste controle (Fermat's stelling)**: Bereken $a^q \pmod{n}$. Als dit gelijk is aan 1, retourneert het algoritme "inconclusief", wat betekent dat $n$ mogelijk een priemgetal is [11](#page=11). 4. **Verdere controles (kwadraten)**: Voor $j$ van 0 tot $k-1$ wordt de reeks kwadraten $a^{2^j q} \pmod{n}$ berekend [11](#page=11). * Als tijdens deze reeks een waarde wordt gevonden die gelijk is aan $n-1$ (wat equivalent is aan $-1 \pmod{n}$), retourneert het algoritme "inconclusief". Dit komt omdat als $a^{2^j q} \equiv n-1 \pmod{n}$, dan is het kwadraat $(a^{2^j q})^2 \equiv (n-1)^2 \equiv (-1)^2 \equiv 1 \pmod{n}$. Als de test verder was gegaan en de waarde 1 zou zijn tegengekomen zonder eerst $n-1$ te zien, dan zou dit aantonen dat $n$ samengesteld is [11](#page=11). 5. **Samengesteld getal**: Als geen van de bovenstaande voorwaarden leidt tot een "inconclusief" resultaat na het doorlopen van de $k$ stappen, retourneert het algoritme "samengesteld", wat betekent dat $n$ definitief geen priemgetal is [11](#page=11). **Het belang van $n-1$**: De reden dat de test stopt bij $j = k-1$ en kijkt naar $n-1$ in plaats van 1, is om te voorkomen dat een samengesteld getal ten onrechte als priem wordt beschouwd. Als tijdens het kwadrateren van de reeks de waarde 1 wordt bereikt, maar de vorige stap niet $n-1$ was, dan is $n$ samengesteld. > **Tip**: Het algoritme streeft ernaar om een samengesteld getal te identificeren. Als het een getal niet kan bewijzen als samengesteld, beschouwt het het als "inconclusief", wat een indicatie is dat het waarschijnlijk een priemgetal is. #### 3.1.2 Output van het algoritme Het Miller-Rabin algoritme kan twee resultaten opleveren [12](#page=12): * **Samengesteld**: Als $n$ definitief geen priemgetal is. * **Inconclusief**: Als $n$ mogelijk wel of niet een priemgetal is. ### 3.2 Probabilistische aard en foutkansen Het Miller-Rabin algoritme is een probabilistische methode, wat betekent dat er een kleine kans is dat het een samengesteld getal ten onrechte als "inconclusief" classificeert [12](#page=12). #### 3.2.1 Kans op fouten Voor een oneven getal $n$ dat niet priem is, en een willekeurig gekozen getal $a$ met $1 < a < n-1$, is de kans dat het Miller-Rabin testresultaat "inconclusief" is (d.w.z. faalt om aan te tonen dat $n$ niet priem is) kleiner dan $1/4$ [13](#page=13). Als $t$ verschillende waarden van $a$ worden gekozen, is de kans dat een niet-priemgetal alle $t$ tests doorstaat kleiner dan $(1/4)^t = 2^{-2t}$ [13](#page=13). * Voor $t=10$ is de kans dat een niet-priemgetal alle tien tests doorstaat minder dan $10^{-6}$ [13](#page=13). * Voor een hogere betrouwbaarheid wordt een voldoende grote waarde van $t$ gekozen [13](#page=13). **Belangrijke overweging**: De bovengenoemde kansen gelden wanneer we één specifiek getal $n$ testen. Als het algoritme wordt gebruikt om daadwerkelijk een priemgetal te vinden, door te blijven selecteren en testen totdat een "inconclusief" resultaat wordt verkregen voor alle geteste $a$-waarden, dan kunnen de kansen op fouten anders uitpakken en zelfs slechter zijn dan de theoretische bovengrenzen. Voor getallen van 600 bits is de kans bijvoorbeeld niet kleiner dan $2^{-1200}$, maar de werkelijke bovengrens is $2^{-75}$ [13](#page=13). #### 3.2.2 Adversariële scenario's In een adversariële setting, waarbij een tegenstander probeert om het algoritme te misleiden, is het gebruik van Miller-Rabin alleen niet altijd aanbevolen. In dergelijke gevallen wordt het Baillie-Pomerance-Selfridge-Wagstaff (Baillie-PSW) test als alternatief genoemd, omdat het meer robuust kan zijn. De worst-case bounds voor foutkansen worden dan belangrijker geacht; voor het verkrijgen van een betrouwbaarheid van $2^{-128}$ zijn bijvoorbeeld 64 iteraties nodig [13](#page=13). > **Tip**: Om een hoge mate van zekerheid te verkrijgen dat een oneven getal $n$ een priemgetal is, is het essentieel om het Miller-Rabin algoritme met een voldoende aantal verschillende willekeurige waarden van $a$ uit te voeren. ### 3.3 Historische context en alternatieven Vóór 2002 waren de meeste algoritmen voor het testen van de primaliteit van grote getallen, inclusief Miller-Rabin, probabilistisch [12](#page=12). * **AKS algoritme**: In 2002 ontwikkelden Agrawal, Kayal en Saxena een deterministisch algoritme (AKS) dat efficiënt de primaliteit van grote getallen kan bepalen. Hoewel het de eerste deterministische primality test was, blijkt het niet zo efficiënt te zijn als Miller-Rabin en wordt het in de praktijk weinig gebruikt [12](#page=12). * **ECPT (ECPP) en APR**: Na AKS zijn er efficiëntere deterministische methoden gevonden, zoals ECPP (elliptic curve primality proving) en APR (Adleman–Pomerance–Rumely primality test). Deze worden vaker gebruikt dan AKS [12](#page=12). * **Hybride aanpak**: In de praktijk wordt vaak eerst Miller-Rabin gebruikt. Alleen als Miller-Rabin met een hoge waarschijnlijkheid aangeeft dat een getal priem is, wordt een meer rigoureuze test zoals ECPP uitgevoerd [12](#page=12). * **Baillie-PSW test**: Dit is een ander probabilistisch algoritme dat Fermat's stelling combineert met Lucas-tests om samengestelde getallen te detecteren die typische primality tests doorstaan [12](#page=12). Ondanks de beschikbaarheid van deterministische algoritmen, blijft Miller-Rabin populair vanwege zijn efficiëntie, vooral in combinatie met een gepaste aantal iteraties om een hoge betrouwbaarheid te bereiken [12](#page=12). --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Priemgetal | Een geheel getal groter dan 1 dat alleen deelbaar is door ±1 en zichzelf. Priemgetallen zijn fundamenteel in de getaltheorie en cryptografie. | | Fundamentele stelling van de rekenkunde | Stelt dat elk geheel getal groter dan 1 uniek kan worden ontbonden in een product van priemgetallen, ongeacht de volgorde van de factoren. Dit principe is essentieel voor veel cryptografische algoritmen. | | Natuurlijke logaritme (ln) | De logaritme met grondtal e (ongeveer 2.71). Het vertegenwoordigt de exponent waartoe e moet worden verheven om de invoer te verkrijgen. ln(n) wordt gebruikt om de gemiddelde afstand tussen priemgetallen rond het getal n te schatten. | | Euler-functies (phi-functie, ø(n)) | Telt het aantal positieve gehele getallen kleiner dan n die relatief priem zijn met n (d.w.z. geen gemeenschappelijke delers hebben behalve 1). Voor een priemgetal p geldt ø(p) = p-1. | | Stelling van Fermat (kleine stelling van Fermat) | Stelt dat als p een priemgetal is en a een positief geheel getal dat niet deelbaar is door p, dan is a^(p-1) ≡ 1 (mod p). Dit is een cruciaal concept in cryptografie. | | Euler's stelling | Een generalisatie van de kleine stelling van Fermat. Voor elk paar getallen a en n die relatief priem zijn, geldt a^ø(n) ≡ 1 (mod n). | | Relatief priem | Twee getallen worden relatief priem genoemd als hun grootste gemene deler (GGD) gelijk is aan 1. Ze hebben dus geen andere gemeenschappelijke delers dan 1. | | Modulo-operatie (mod) | De bewerking die de rest oplevert na deling van een getal door een ander getal. Bijvoorbeeld, 10 mod 3 is 1, omdat 10 gedeeld door 3 drie keer gaat met een rest van 1. | | Miller-Rabin algoritme | Een probabilistisch algoritme dat wordt gebruikt om te bepalen of een groot getal waarschijnlijk een priemgetal is. Het test de primaliteit door Fermat's stelling te controleren voor willekeurig gekozen getallen. | | Probabilistisch algoritme | Een algoritme dat een willekeurige invoer gebruikt en dat bij elke uitvoering een ander resultaat kan produceren. In het geval van primaliteitstesten, kunnen ze een getal als waarschijnlijk priem aanmerken, maar nooit met 100% zekerheid. | | Deterministisch algoritme | Een algoritme dat bij dezelfde invoer altijd hetzelfde resultaat produceert. Het AKS-algoritme is bijvoorbeeld het eerste deterministische algoritme voor primaliteitstesten. |