PricingLoginStart free
Cryptology Academy · Les

GCD, de totiëntfunctie van Euler en getaltheorie

Pas GCD en de totiëntfunctie van Euler toe op echte cryptografische problemen.

Les 4 van 413 stappen

GCD, de totiëntfunctie van Euler en getaltheorie is een gratis Cryptology Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Cryptology Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Cryptology Academy bevat in totaal 4 lessen.

Welkom

De GGD en de Euler-phi-functie zijn essentiële hulpmiddelen in RSA en veel andere systemen met openbare sleutels. Laten we ze aan de hand van voorbeelden beheersen.

Grootste gemene deler (GCD)

GCD(a, b) is het grootste gehele getal dat zowel a als b zonder rest deelt. GCD(12, 8) = 4. Als GCD(a, m) = 1, noemen we a en m onderling ondeelbaar of relatief priem.

Algoritme van Euclides

GCD(a, b) = GCD(b, a mod b), met als basisgeval GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Uitgebreid algoritme van Euclides

De uitgebreide versie vindt gehele getallen x en y waarvoor ax + by = GCD(a,b). Als GCD(a,m)=1, is x het modulaire inverse van a modulo m. Zo berekent RSA privésleutels.

Euler-phi-functie φ(n)

φ(n) telt de gehele getallen van 1 tot en met n die onderling ondeelbaar zijn met n. φ(10) = 4, omdat {1, 3, 7, 9} onderling ondeelbaar zijn met 10. φ(p) = p-1 voor elk priemgetal p.

Phi van een product

Voor RSA: n = p×q (p,q priem). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Voorbeeld: p=5, q=11: φ(55) = 4×10 = 40. Daarom breekt het factoriseren van n RSA — het onthult φ(n).

Stelling van Euler

Als GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). Dit vormt de wiskundige basis voor RSA-ontcijfering: M = C^d mod n, omdat e×d ≡ 1 (mod φ(n)).

d berekenen in RSA

Kies e = 65537, een veelgebruikte openbare RSA-exponent. Bereken d = e^(-1) mod φ(n) met het uitgebreide algoritme van Euclides. Controleer of e×d mod φ(n) == 1.

Phi in Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Carmichaels lambdafunctie

Moderne RSA gebruikt de lambdafunctie van Carmichael λ(n) = lcm(p-1, q-1) in plaats van φ(n). Deze levert een kleinere, equivalente modulus op. PKCS#1 v2 en NIST bevelen λ(n) aan.

Samenvatting van de praktische toepassing

GGD: controleer of e onderling ondeelbaar is met φ(n). Uitgebreid algoritme van Euclides: bereken de privésleutel d. Phi: bepaal de exponentgroep voor modulaire machtsverheffing. Alle drie worden gebruikt bij het genereren van elke RSA-sleutel.

Korte controle

Wat is φ(n) voor RSA met p=7 en q=11?
Beantwoord dit in de interactieve les

Samenvatting

Uitstekend! De GGD, het algoritme van Euclides en de Euler-phi-functie zitten nu in je gereedschapskist. Vervolgens bestuderen we XOR en bitsgewijze bewerkingen — de bouwstenen van symmetrische versleutelingen.
Gratis beginnen

Leer Cryptology Academy met een AI-tutor — gratis

Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.

Cursussen
67
Lessen
261
Gratis beginnen met lerenBekijk de volledige cursus

Veelgestelde vragen

Is de les “GCD, de totiëntfunctie van Euler en getaltheorie” gratis?

Ja — de volledige tekst van “GCD, de totiëntfunctie van Euler en getaltheorie” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Cryptology Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Cryptology Academy bevat in totaal 4 lessen.

Wat leer ik in “GCD, de totiëntfunctie van Euler en getaltheorie”?

Pas GCD en de totiëntfunctie van Euler toe op echte cryptografische problemen. Je oefent met Cryptology Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.

Heb ik ervaring nodig om met Cryptology Academy te beginnen?

Ervaring vooraf is niet nodig. Cryptology Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.

Hoe lang duurt de les “GCD, de totiëntfunctie van Euler en getaltheorie”?

De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.

Kan ik code schrijven en uitvoeren in deze les over Cryptology Academy?

Ja. Elke les over Cryptology Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.

Alle lessen in deze cursus

  1. Binaire en hexadecimale basisprincipes
  2. Basisprincipes van modulaire rekenkunde
  3. Priemgetallen en factorisatie
  4. GCD, de totiëntfunctie van Euler en getaltheorie
← Terug naar Cryptology Academy