Modulare Arithmetik

• Modulo-Rechnung ist das mathematische Fundament fast aller modernen Kryptoverfahren (RSA, DH, ECC).
• Kongruenz $a \equiv b \pmod n$ bedeutet: $n$ teilt $a-b$. Damit rechnet man in der Restklassenmenge $\mathbb{Z}_n$.
• Multiplikative Inverse $a^{-1} \bmod n$ existiert genau dann, wenn $\gcd(a,n)=1$. Berechnung mit dem erweiterten Euklid.
• Eulersche $\varphi$-Funktion, Fermat und Euler liefern schnelle Regeln für Potenzen mod $n$ – zentral für RSA.
• Square-and-Multiply und Miller-Rabin sind die algorithmischen Werkzeuge der Praxis.

1. Modulo-Operation und Kongruenz

Die Modulo-Operation liefert den Rest einer ganzzahligen Division:

$$a \bmod n = r \quad \text{mit} \quad a = q \cdot n + r,\ 0 \leq r < n$$

Zwei Zahlen $a, b$ heißen kongruent modulo $n$, geschrieben

$$a \equiv b \pmod n \iff n \mid (a-b)$$

Beispiel: $17 \equiv 5 \pmod{12}$, weil $17 - 5 = 12$ durch $12$ teilbar ist.

2. Rechenregeln in $\mathbb{Z}_n$

In der Restklassenmenge $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$ gelten:

• $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$
• $(a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n$
• $a^k \bmod n = (a \bmod n)^k \bmod n$

Das erlaubt es, Zwischenergebnisse jederzeit zu reduzieren – zentrales Prinzip für effizientes Rechnen mit riesigen Zahlen.

3. Größter gemeinsamer Teiler und Euklidischer Algorithmus

Der $\gcd(a, b)$ ist die größte Zahl, die sowohl $a$ als auch $b$ teilt. Der euklidische Algorithmus nutzt:

$$\gcd(a, b) = \gcd(b, a \bmod b), \quad \gcd(a, 0) = a$$

Beispiel $\gcd(30, 12)$: $30 = 2\cdot 12 + 6$, $12 = 2 \cdot 6 + 0 \Rightarrow \gcd = 6$.

4. Erweiterter Euklidischer Algorithmus

Findet zusätzlich Koeffizienten $u, v \in \mathbb{Z}$ mit

$$a \cdot u + n \cdot v = \gcd(a, n)$$

Ist $\gcd(a, n) = 1$, so gilt $a \cdot u \equiv 1 \pmod n$ – d.h. $u$ ist die multiplikative Inverse von $a$ modulo $n$.

Anwendung: Entschlüsselung bei affiner Chiffre, RSA-Schlüsselerzeugung ($d = e^{-1} \bmod \varphi(n)$).

5. Multiplikative Inverse in $\mathbb{Z}_n$

Ein Element $a \in \mathbb{Z}_n$ besitzt genau dann eine Inverse $a^{-1}$, wenn

$$\gcd(a, n) = 1$$

Die Menge aller invertierbaren Elemente bildet die Gruppe $\mathbb{Z}_n^*$. Ihre Größe ist $|\mathbb{Z}_n^*| = \varphi(n)$.

5b. Multiplikative Inverse per Hand — 3 Methoden Klausur

Gesucht: $a^{-1} \bmod n$, also die Zahl $x \in \{1, \dots, n-1\}$ mit $a \cdot x \equiv 1 \pmod n$. Je nach Größe von $n$ nutzt man eine andere Methode.

Methode 1 · Ausprobieren (nur für kleine $n$)

Für $n \leq 30$ schneller als jede Formel. Rechne $a \cdot k \bmod n$ für $k = 1, 2, 3, \dots$ bis das Ergebnis $1$ ist.

Beispiel: $3^{-1} \bmod 11$.

$3 \cdot 1 = 3 \bmod 11 = 3$
$3 \cdot 2 = 6 \bmod 11 = 6$
$3 \cdot 3 = 9 \bmod 11 = 9$
$3 \cdot 4 = 12 \bmod 11 = \mathbf{1}$ ✓
→ $3^{-1} \equiv 4 \bmod 11$

Probe: $3 \cdot 4 = 12 = 1 \cdot 11 + 1 \equiv 1$ ✓

Methode 2 · Erweiterter Euklid (Pagnia-Rekursion, Klausur-Standard)

Für mittlere $n$ die verlässliche Methode. Zwei-Spalten-Tabelle plus Rückwärts-Rekursion.

Rezept:

1. Zwei-Spalten-Tabelle: links $\bmod$-Reste $r_i$, rechts $\text{div}$-Quotienten $x_i$. Stop bei Rest $1$.
2. Rekursion: $A_{t+2} = 0$, $A_{t+1} = 1$, dann $A_k = A_{k+2} - x_k \cdot A_{k+1}$ für $k = t, \dots, 0$.
3. Ergebnis: $a^{-1} = A_0 \bmod n$. Falls $A_0$ negativ, einfach $n$ addieren.

Beispiel: $17^{-1} \bmod 43$.

Schritt 1 — Tabelle:

$43 \bmod 17 = 9 \quad|\quad 43 \div 17 = 2 \quad\Rightarrow r_0 = 9,\ x_0 = 2$
$17 \bmod 9 = 8 \quad|\quad 17 \div 9 = 1 \quad\Rightarrow r_1 = 8,\ x_1 = 1$
$9 \bmod 8 = 1 \quad|\quad 9 \div 8 = 1 \quad\Rightarrow r_2 = 1,\ x_2 = 1 \quad$ (Stop, Rest 1)

Schritt 2 — Rekursion (mit $t = 2$):

$A_4 = 0,\ A_3 = 1$
$A_2 = A_4 - x_2 \cdot A_3 = 0 - 1 \cdot 1 = -1$
$A_1 = A_3 - x_1 \cdot A_2 = 1 - 1 \cdot (-1) = 2$
$A_0 = A_2 - x_0 \cdot A_1 = -1 - 2 \cdot 2 = -5$

Schritt 3 — Vorzeichen korrigieren: $-5 \bmod 43 = -5 + 43 = 38$.

→ $17^{-1} \equiv \mathbf{38} \bmod 43$. Probe: $17 \cdot 38 = 646 = 15 \cdot 43 + 1 \equiv 1 \bmod 43$ ✓

Beispiel 2 (RSA-Klassiker): $7^{-1} \bmod 120$.

$120 \bmod 7 = 1 \quad|\quad 120 \div 7 = 17 \quad\Rightarrow r_0 = 1,\ x_0 = 17 \quad$ (Stop nach nur 1 Schritt!)
$A_2 = 0,\ A_1 = 1$
$A_0 = A_2 - x_0 \cdot A_1 = 0 - 17 \cdot 1 = -17$
→ $-17 \bmod 120 = \mathbf{103}$

Probe: $7 \cdot 103 = 721 = 6 \cdot 120 + 1 \equiv 1 \bmod 120$ ✓

Methode 3 · Euler-Satz-Trick (nur wenn $\varphi(n)$ leicht bekannt)

Nach dem Satz von Euler gilt für $\gcd(a, n) = 1$:

$$a^{\varphi(n)} \equiv 1 \bmod n \quad\Rightarrow\quad a^{-1} \equiv a^{\varphi(n) - 1} \bmod n$$

Nützlich, wenn $\varphi(n)$ bekannt ist (z. B. $n$ prim → $\varphi(n) = n-1$).

Beispiel: $3^{-1} \bmod 11$ per Euler.

$\varphi(11) = 10$, also $3^{-1} \equiv 3^{10-1} = 3^9 \bmod 11$.

Square-and-Multiply für $3^9$ mit $9 = 1001_2$:
Start $r = 1$, Bit 1 (MSB): $r = 1 \cdot 3 = 3$
Bit 0: $r = 3^2 = 9 \bmod 11 = 9$
Bit 0: $r = 9^2 = 81 \bmod 11 = 4$
Bit 1: $r = 4^2 \cdot 3 = 48 \bmod 11 = 4$
→ $3^{-1} \equiv \mathbf{4} \bmod 11$ (identisch mit Methode 1)

6. Eulersche $\varphi$-Funktion

$\varphi(n)$ zählt die zu $n$ teilerfremden Zahlen in $\{1, 2, \dots, n-1\}$.

• Primzahl $p$: $\varphi(p) = p - 1$
• Produkt zweier verschiedener Primzahlen: $\varphi(p \cdot q) = (p-1)(q-1)$
• Allgemein: $\varphi(n) = n \cdot \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right)$

Beispiel: $\varphi(15) = \varphi(3\cdot 5) = 2 \cdot 4 = 8$.

7. Kleiner Satz von Fermat

Für Primzahl $p$ und $\gcd(a, p) = 1$ gilt:

$$a^{p-1} \equiv 1 \pmod p$$

Daraus folgt $a^p \equiv a \pmod p$ – nützlich zur Reduktion von Exponenten.

8. Satz von Euler (Verallgemeinerung)

Für beliebiges $n$ und $\gcd(a, n) = 1$:

$$a^{\varphi(n)} \equiv 1 \pmod n$$

Fundament von RSA: Erlaubt das Zurückrechnen $c^d \equiv m \pmod n$ mit $d \cdot e \equiv 1 \pmod{\varphi(n)}$.

9. Square-and-Multiply

Berechnet $a^k \bmod n$ in $\mathcal{O}(\log k)$ Schritten statt $k$ Multiplikationen. Vorgehen:

1. Binärdarstellung des Exponenten: $k = (b_t b_{t-1} \dots b_0)_2$
2. Von links nach rechts: Ergebnis quadrieren, bei Bit $=1$ zusätzlich mit $a$ multiplizieren, jeweils $\bmod n$.

Beispiel $3^{13} \bmod n$: $13 = 1101_2$ ergibt Schritte quadriere / multipliziere / quadriere / quadriere-mult. / quadriere-mult.

10. Miller-Rabin-Primzahltest

Probabilistischer Test, ob eine Zahl $n$ prim ist. Zerlegung $n - 1 = 2^s \cdot d$ mit ungeradem $d$. Für zufällige Basis $a$ prüft man

$$a^d \bmod n \quad \text{und} \quad a^{2^r d} \bmod n\ \ (r = 0, \dots, s-1)$$

Erscheint in dieser Kette nicht $1$ oder $-1$ (also $n-1$), so ist $n$ sicher zusammengesetzt. Andernfalls wahrscheinlich prim mit Fehler $\leq 4^{-k}$ nach $k$ Runden.

11. Quadratisches Zahlensieb (Faktorisierung) Klausur

Standardverfahren zur Faktorisierung bis ca. $10^{110}$ (für größere Zahlen: GNFS). Grundlage für RSA-Sicherheit — Pagnia stellt es in Folie S.84 vor.

Grundidee: Finde zwei Zahlen $a, b$ mit

$$a^2 \equiv b^2 \pmod x$$

Daraus folgt $(a^2 - b^2) \equiv 0 \bmod x$, also $(a+b)(a-b) \equiv 0 \bmod x$. Damit sind $(a+b)$ und $(a-b)$ Teiler von $x$ (oder Vielfache eines Teilers).

Pagnias Beispiel (Folie S.84): Faktorisiere $x = 35$.

1. Wähle $a, b$ so, dass $a^2 - b^2$ ein Vielfaches von $35$ ist.
2. Beobachtung: $35 + 1 = 36 = 6^2$ ist eine Quadratzahl. Wähle $a = 6$, $b = 1$.
3. $a^2 - b^2 = 36 - 1 = 35 \equiv 0 \bmod 35$ ✓
4. Teiler: $a - b = 5$ und $a + b = 7$. Und tatsächlich $5 \cdot 7 = 35$.

Weitere Übungsbeispiele (aus der Folie): $x = 45$, $x = 407$.