Getaltheorie & modulair rekenen: oefenopgaven met stapsgewijze oplossingen

1Resten en congruenties

Delen van a door n geeft een quotiënt q en een rest r: a = q·n + r met 0 ≤ r < n. De rest wordt geschreven als a mod n. Voor een negatief getal is q ook negatief: −3 = −1·7 + 4, dus −3 mod 7 = 4.

Twee getallen zijn congruent modulo n, a ≡ b (mod n), als ze dezelfde rest geven, dat wil zeggen als n een deler is van a − b.

Resten kunnen bij elke stap gereduceerd worden, waardoor de getallen klein blijven:

Bijvoorbeeld 47·58 mod 9: 47 ≡ 2 en 58 ≡ 4, dus 47·58 ≡ 8 (mod 9).

2Het algoritme van Euclides

De grootste gemene deler ggd(a, b) is het grootste getal dat beide deelt. Het algoritme van Euclides gebruikt ggd(a, b) = ggd(b, a mod b):

1. Deel: a = q·b + r.
2. Vervang (a, b) door (b, r).
3. Herhaal tot de rest 0 is. De laatste rest ongelijk aan nul is de ggd.

Het kleinste gemene veelvoud volgt hieruit: kgv(a, b) = a·b / ggd(a, b).

3Inversen en het uitgebreide algoritme

De inverse van a modulo n is het getal x met a·x ≡ 1 (mod n). Hij bestaat precies dan als ggd(a, n) = 1.

Het uitgebreide algoritme van Euclides laat Euclides lopen op (n, a) en houdt voor elke rest een coëfficiënt t bij, zodat elke rest r ≡ t·a (mod n). Begin met t = 0 voor n en t = 1 voor a; elke nieuwe t is de t twee rijen hoger min q keer de t één rij hoger. Als de rest 1 verschijnt, is zijn t de inverse.

Met de inverse wordt een congruentie a·x ≡ b (mod n) opgelost door x ≡ a⁻¹·b. Als d = ggd(a, n) groter is dan 1, zijn er d oplossingen als d een deler is van b, en anders geen.

Twee congruenties met onderling ondeelbare moduli, x ≡ r₁ (mod m₁) en x ≡ r₂ (mod m₂), hebben precies één oplossing modulo m₁·m₂ (de Chinese reststelling). Schrijf x = r₁ + m₁k en los op voor k.

4Modulaire machten en RSA

Herhaald kwadrateren berekent aᵏ mod n snel: schrijf k binair, bepaal a, a², a⁴, a⁸, … mod n door te kwadrateren en te reduceren, en vermenigvuldig de machten waarvan de bit 1 is.

De kleine stelling van Fermat: voor een priemgetal p dat a niet deelt, geldt aᵖ⁻¹ ≡ 1 (mod p). De exponent kan dus modulo p − 1 gereduceerd worden.

RSA bouwt een sleutel uit twee priemgetallen p en q:

1. n = p·q en φ(n) = (p − 1)(q − 1).
2. Kies e met ggd(e, φ(n)) = 1; (n, e) is de publieke sleutel.
3. Bereken d = e⁻¹ mod φ(n): de privésleutel.
4. Versleutel c = mᵉ mod n; ontsleutel m = cᵈ mod n.

Eulers φ(n) telt de getallen van 1 tot n die onderling ondeelbaar zijn met n: φ(p) = p − 1 voor een priemgetal, φ(pᵏ) = pᵏ − pᵏ⁻¹, en φ is multiplicatief voor onderling ondeelbare factoren.

5Veelgemaakte fouten

• Een negatieve rest geven voor een negatief getal: −17 mod 5 is 3, niet −2.
• Euclides stoppen bij de eerste rest in plaats van bij de laatste rest ongelijk aan nul.
• Vergeten n op te tellen bij een negatieve coëfficiënt uit het uitgebreide algoritme.
• De RSA-exponent d berekenen modulo n in plaats van modulo φ(n).
• Een exponent modulo p reduceren in plaats van modulo p − 1 bij de stelling van Fermat.

6Hoe tentamenvragen eruitzien

• Makkelijk: ggd en resten. Je laat het algoritme van Euclides lopen voor een ggd of kgv, vindt resten van negatieve getallen en reduceert sommen en producten modulo n.
• Gemiddeld: inversen en congruenties. Je vindt modulaire inversen met het uitgebreide algoritme, lost lineaire congruenties op, combineert twee congruenties met de Chinese reststelling en berekent Eulers φ(n).
• Moeilijk: modulaire machten en RSA. Je gebruikt herhaald kwadrateren en de stelling van Fermat, lost congruenties met meerdere oplossingen op en vindt RSA-privé-exponenten, versleutelde teksten en ontsleutelde berichten.