Zahlentheorie & modulare Arithmetik: Übungsaufgaben mit Schritt-für-Schritt-Lösungen
Auch genannt: modulare Arithmetik · euklidischer Algorithmus
Kostenlose Übungsaufgaben zu Zahlentheorie & modulare Arithmetik mit Skizzen, Tipps und vollständigen Musterlösungen. Jedes Mal neue Werte, in drei Stufen: ggT und Reste, Inverse und Kongruenzen, modulare Potenzen und RSA.
So löst du Aufgaben zu Zahlentheorie & modulare Arithmetik
Reduziere zuerst jede Zahl modulo n; die Reste liegen zwischen 0 und n − 1.
Teile für einen ggT wiederholt mit dem euklidischen Algorithmus; der letzte Rest ungleich null ist der ggT.
Führe für ein Inverses den erweiterten Algorithmus aus und behalte den Koeffizienten von a; addiere n, falls er negativ ist.
Löse a·x ≡ b, indem du mit a⁻¹ multiplizierst; kombiniere zwei Kongruenzen, indem du x = r₁ + m₁k schreibst.
Schreibe bei Potenzen den Exponenten binär und quadriere wiederholt; bei RSA gilt d = e⁻¹ mod φ(n) mit φ(n) = (p − 1)(q − 1).
Häufige Fehler
Bei einer negativen Zahl einen negativen Rest angeben.
Den euklidischen Algorithmus beim ersten Rest abbrechen.
Das Inverse negativ lassen, statt n zu addieren.
Den RSA-Exponenten d modulo n statt modulo φ(n) bilden.
Beim kleinen Satz von Fermat den Exponenten modulo p statt modulo p − 1 reduzieren.
Wichtige Formeln
Division mit Rest
a = q·n + r, 0 ≤ r < n
Euklid
gcd(a, b) = gcd(b, a mod b)
Kleinstes gemeinsames Vielfaches
lcm(a, b) = a·b/gcd(a, b)
Inverse
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Lineare Kongruenz
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Eulersche φ-Funktion
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Zahlentheorie & modulare Arithmetik von Grund auf lernen
1Reste und Kongruenzen
Teilt man a durch n, erhält man einen Quotienten q und einen Rest r: a = q·n + r mit 0 ≤ r < n. Der Rest wird als a mod n geschrieben. Bei einer negativen Zahl ist auch q negativ: −3 = −1·7 + 4, also −3 mod 7 = 4.
Zwei Zahlen sind modulo n kongruent, a ≡ b (mod n), wenn sie denselben Rest lassen, also wenn n die Differenz a − b teilt.
Reste lassen sich in jedem Schritt reduzieren, wodurch die Zahlen klein bleiben:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, ebenso für a·b
Zum Beispiel 47·58 mod 9: 47 ≡ 2 und 58 ≡ 4, also 47·58 ≡ 8 (mod 9).
Selbsttest Was ist −17 mod 5?
2
3
−2
−3
Antwort: 3. −17 = −4·5 + 3, der Rest ist also 3. Die Antwort 2 ist 17 mod 5; ein Rest ist nie negativ.
2Der euklidische Algorithmus
Der größte gemeinsame Teiler ggT(a, b) ist die größte Zahl, die beide teilt. Der euklidische Algorithmus nutzt ggT(a, b) = ggT(b, a mod b):
Dividiere: a = q·b + r.
Ersetze (a, b) durch (b, r).
Wiederhole, bis der Rest 0 ist. Der letzte Rest ungleich null ist der ggT.
Das kleinste gemeinsame Vielfache folgt daraus: kgV(a, b) = a·b / ggT(a, b).
Selbsttest Was ist ggT(84, 36)?
12
252
4
6
Antwort: 12. 84 = 2·36 + 12 und 36 = 3·12 + 0, also ist der ggT 12. 252 ist das kleinste gemeinsame Vielfache, 84·36/12.
3Inverse und der erweiterte Algorithmus
Das Inverse von a modulo n ist die Zahl x mit a·x ≡ 1 (mod n). Es existiert genau dann, wenn ggT(a, n) = 1.
Der erweiterte euklidische Algorithmus führt Euklid auf (n, a) aus und führt zu jedem Rest einen Koeffizienten t mit, sodass jeder Rest r ≡ t·a (mod n) erfüllt. Beginne mit t = 0 für n und t = 1 für a; jedes neue t ist das t zwei Zeilen darüber minus q mal das t eine Zeile darüber. Wenn der Rest 1 erscheint, ist sein t das Inverse.
Mit dem Inversen löst man eine Kongruenz a·x ≡ b (mod n) durch x ≡ a⁻¹·b. Ist d = ggT(a, n) größer als 1, gibt es d Lösungen, falls d die Zahl b teilt, und sonst keine.
Zwei Kongruenzen mit teilerfremden Moduln, x ≡ r₁ (mod m₁) und x ≡ r₂ (mod m₂), haben genau eine Lösung modulo m₁·m₂ (der chinesische Restsatz). Schreibe x = r₁ + m₁k und löse nach k auf.
Das wiederholte Quadrieren berechnet aᵏ mod n schnell: Schreibe k binär, bestimme a, a², a⁴, a⁸, … mod n durch Quadrieren und Reduzieren und multipliziere die Potenzen, deren Bit 1 ist.
Der kleine Satz von Fermat: Für eine Primzahl p, die a nicht teilt, gilt aᵖ⁻¹ ≡ 1 (mod p). Der Exponent lässt sich also modulo p − 1 reduzieren.
RSA erzeugt einen Schlüssel aus zwei Primzahlen p und q:
n = p·q und φ(n) = (p − 1)(q − 1).
Wähle e mit ggT(e, φ(n)) = 1; (n, e) ist der öffentliche Schlüssel.
Berechne d = e⁻¹ mod φ(n): den privaten Schlüssel.
Verschlüsseln: c = mᵉ mod n; entschlüsseln: m = cᵈ mod n.
Eulers φ(n) zählt die Zahlen von 1 bis n, die zu n teilerfremd sind: φ(p) = p − 1 für eine Primzahl, φ(pᵏ) = pᵏ − pᵏ⁻¹, und φ ist für teilerfremde Faktoren multiplikativ.
Selbsttest Ein RSA-Schlüssel verwendet p = 5, q = 11 und e = 3. Was ist d?
13
27
37
3
Antwort: 27. φ(n) = 4·10 = 40, und 3·27 = 81 = 2·40 + 1, also d = 27. Das Inverse von 3 modulo n = 55 wäre 37, aber d wird modulo φ(n) gebildet.
5Häufige Fehler
Bei einer negativen Zahl einen negativen Rest angeben: −17 mod 5 ist 3, nicht −2.
Den euklidischen Algorithmus beim ersten Rest statt beim letzten Rest ungleich null abbrechen.
Vergessen, zu einem negativen Koeffizienten aus dem erweiterten Algorithmus n zu addieren.
Den RSA-Exponenten d modulo n statt modulo φ(n) berechnen.
Beim Satz von Fermat einen Exponenten modulo p statt modulo p − 1 reduzieren.
6So sehen Prüfungsaufgaben aus
Leicht: ggT und Reste. Du führst den euklidischen Algorithmus für einen ggT oder ein kgV aus, bestimmst Reste negativer Zahlen und reduzierst Summen und Produkte modulo n.
Mittel: Inverse und Kongruenzen. Du bestimmst modulare Inverse mit dem erweiterten Algorithmus, löst lineare Kongruenzen, kombinierst zwei Kongruenzen mit dem chinesischen Restsatz und berechnest Eulers φ(n).
Schwer: modulare Potenzen und RSA. Du nutzt wiederholtes Quadrieren und den Satz von Fermat, löst Kongruenzen mit mehreren Lösungen und bestimmst private RSA-Exponenten, Geheimtexte und entschlüsselte Nachrichten.
Bestimme (914·953) mod 11, ohne die großen Zahlen auszumultiplizieren: Reduziere zuerst.
n = 11
Gesucht: (914·953) mod 11
Tipps anzeigen
(x·y) mod n = ((x mod n)·(y mod n)) mod n, und dasselbe gilt für Summen.
914 mod 11 = 1, 953 mod 11 = 7.
Reduziere das Produkt der Reste modulo 11.
Antwort und Schritt-für-Schritt-Lösung anzeigen
Teilbarkeit und Reste: a mod n ist der Rest r mit 0 ≤ r < n und a = q·n + r, auch wenn a negativ ist. Der euklidische Algorithmus findet ggT(a, b), indem er a = q·b + r wiederholt und (a, b) durch (b, r) ersetzt; der letzte Rest ungleich null ist der ggT. Dann gilt kgV(a, b) = a·b/ggT(a, b). Reste lassen sich in jedem Schritt reduzieren: (a + b) mod n und (a·b) mod n hängen nur von a mod n und b mod n ab.
Jede Zahl reduzieren
914 ≡ 1, 953 ≡ 7 (mod 11)
Zusammenfassen
1·7 = 7 ≡ 7 (mod 11)
Antwort
(914·953) mod 11 = 7
Beispiel 2Mittel
Bestimme die Eulersche φ-Funktion φ(637), die Anzahl der ganzen Zahlen von 1 bis 637, die zu 637 teilerfremd sind.
n = 637 = 72·13
Gesucht: φ(637)
Tipps anzeigen
Zerlege n in Primfaktoren: 637 = 72·13.
φ ist für teilerfremde Faktoren multiplikativ, und φ(pᵏ) = pᵏ − pᵏ⁻¹.
φ(n) = n·∏(1 − 1/p).
Antwort und Schritt-für-Schritt-Lösung anzeigen
Inverse und Kongruenzen: a hat genau dann ein Inverses modulo n, wenn ggT(a, n) = 1. Der erweiterte euklidische Algorithmus schreibt 1 = s·n + t·a, und dann ist a⁻¹ ≡ t (mod n). Eine Kongruenz a·x ≡ b (mod n) mit ggT(a, n) = 1 hat die Lösung x ≡ a⁻¹·b. Zwei Kongruenzen x ≡ r₁ (mod m₁) und x ≡ r₂ (mod m₂) mit teilerfremden Moduln haben eine Lösung modulo m₁·m₂ (chinesischer Restsatz). Eulers φ(n) zählt die Zahlen von 1 bis n, die zu n teilerfremd sind: φ(n) = n·∏(1 − 1/p).
Primfaktoren
637 = 72·13
φ-Wert
φ(637) = φ(49)·φ(13) = 42·12 = 504
Antwort
φ(637) = 504
Beispiel 3Schwer
Ein RSA-Schlüssel verwendet p = 13, q = 37 und e = 23. Entschlüssele den Geheimtext c = 225: Bestimme die Nachricht m.
p = 13q = 37e = 23c = 225
Gesucht: m
Tipps anzeigen
n = 481, φ(n) = 432.
d = e⁻¹ mod φ(n) = 263.
m = cd mod n = 225263 mod 481: wiederholtes Quadrieren verwenden.
Antwort und Schritt-für-Schritt-Lösung anzeigen
Modulare Potenzen und RSA: Berechne aᵏ mod n durch wiederholtes Quadrieren: Schreibe k binär, quadriere, reduziere nach jedem Schritt und multipliziere die Potenzen, deren Bit 1 ist. Fermat: aᵖ⁻¹ ≡ 1 (mod p) für eine Primzahl p, die a nicht teilt, der Exponent lässt sich also modulo p − 1 reduzieren. RSA: Wähle Primzahlen p und q, n = p·q und φ(n) = (p − 1)(q − 1); der öffentliche Exponent e ist teilerfremd zu φ(n), und der private Exponent ist d = e⁻¹ mod φ(n). Verschlüssele mit c = mᵉ mod n und entschlüssele mit m = cᵈ mod n.
Privater Exponent
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
Durch wiederholtes Quadrieren entschlüsseln
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
Nachricht
m = 361
Probe: 36123 mod 481 = 225
Antwort
m = 361
Fragen und Antworten
Zahlentheorie & modulare Arithmetik: Worum geht es?
Teilt man a durch n, erhält man einen Quotienten q und einen Rest r: a = q·n + r mit 0 ≤ r < n. Der Rest wird als a mod n geschrieben. Bei einer negativen Zahl ist auch q negativ: −3 = −1·7 + 4, also −3 mod 7 = 4.
Zwei Zahlen sind modulo n kongruent, a ≡ b (mod n), wenn sie denselben Rest lassen, also wenn n die Differenz a − b teilt.
Zahlentheorie & modulare Arithmetik: Wie löst man die Aufgaben Schritt für Schritt?
Reduziere zuerst jede Zahl modulo n; die Reste liegen zwischen 0 und n − 1.
Teile für einen ggT wiederholt mit dem euklidischen Algorithmus; der letzte Rest ungleich null ist der ggT.
Führe für ein Inverses den erweiterten Algorithmus aus und behalte den Koeffizienten von a; addiere n, falls er negativ ist.
Löse a·x ≡ b, indem du mit a⁻¹ multiplizierst; kombiniere zwei Kongruenzen, indem du x = r₁ + m₁k schreibst.
Schreibe bei Potenzen den Exponenten binär und quadriere wiederholt; bei RSA gilt d = e⁻¹ mod φ(n) mit φ(n) = (p − 1)(q − 1).
Zahlentheorie & modulare Arithmetik: Welche Fehler passieren am häufigsten?
Bei einer negativen Zahl einen negativen Rest angeben.
Den euklidischen Algorithmus beim ersten Rest abbrechen.
Das Inverse negativ lassen, statt n zu addieren.
Den RSA-Exponenten d modulo n statt modulo φ(n) bilden.
Beim kleinen Satz von Fermat den Exponenten modulo p statt modulo p − 1 reduzieren.
Zahlentheorie & modulare Arithmetik: Was wird geübt?
Leicht: ggT und Reste
Mittel: Inverse und Kongruenzen
Schwer: modulare Potenzen und RSA
Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort. Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
So funktioniert das Üben
Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort.
Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
Dein Fortschritt, deine Fehler und gespeicherten Aufgaben bleiben erhalten, damit du vor der Prüfung wiederholen kannst.