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)$.

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.