Mathematik Zahlentheorie – Modulare Arithmetik

Sie ist reflexiv (a ≡ a), symmetrisch (a ≡ b ⇒ b ≡ a) und transitiv (a ≡ b ∧ b ≡ c ⇒ a ≡ c) – eine Äquivalenzrelation.

Aus a ≡ b und c ≡ d folgt a + c ≡ b + d und a·c ≡ b·d (mod m) – Rechenregeln bleiben erhalten.

Die Menge aller ganzen Zahlen, die modulo m kongruent zu einer gegebenen Zahl a sind: [a]_m = {a + k·m | k ∈ ℤ}.

Genau m verschiedene Restklassen: [0], [1], …, [m−1]. Sie bilden den Restklassenring ℤ/mℤ.

Eine Zahl a hat genau dann ein Inverses modulo m, wenn gcd(a, m) = 1 gilt – also a und m teilerfremd sind.

Mit dem erweiterten euklidischen Algorithmus: Man bestimmt x, y mit a·x + m·y = gcd(a,m) = 1, dann ist x das Inverse.

Ein System linearer Kongruenzen x ≡ a_i (mod m_i) mit paarweise teilerfremden Moduln m_i hat genau eine Lösung modulo M = ∏ m_i.

Für eine Primzahl p und a mit p ∤ a gilt a^(p−1) ≡ 1 (mod p). Grundlage für Primzahltests und Kryptographie.

φ(n) zählt die Zahlen 1 ≤ k ≤ n, die teilerfremd zu n sind. Für p prim: φ(p) = p−1, φ(p^k) = p^k − p^(k−1).

Für teilerfremde a, n gilt a^φ(n) ≡ 1 (mod n). Verallgemeinert den kleinen fermatschen Satz auf beliebige Moduln.

Man zerlegt den Exponenten binär, quadriert die Basis wiederholt modulo m und multipliziert nur bei gesetzten Bits – Laufzeit O(log e).

Eine Zahl a ist quadratischer Rest modulo p, wenn es ein x mit x^2 ≡ a (mod p) gibt. Das Legendre-Symbol (a/p) zeigt dies an.

Eine Zahl p > 1 ist genau dann prim, wenn (p−1)! ≡ −1 (mod p) gilt. Theoretisch wichtig, praktisch ineffizient für Primzahltests.

RSA nutzt modulare Exponentiation mit großem Modul n = p·q. Verschlüsselung: c ≡ m^e (mod n), Entschlüsselung: m ≡ c^d (mod n) mit e·d ≡ 1 (mod φ(n)).