Mathematik Zahlentheorie – Modulare Arithmetik
Karteikarten zum Thema „Mathematik“ · 15 Karten · von atrio. Beispiele: Was bedeutet a ≡ b (mod m)? · Welche Eigenschaften hat die Kongruenzrelation?
Karten
15 KartenWas bedeutet a ≡ b (mod m)?
Rückseite
a und b sind kongruent modulo m, wenn m die Differenz a − b teilt, also a − b = k·m für ein k ∈ ℤ.
Welche Eigenschaften hat die Kongruenzrelation?
Rückseite
Sie ist reflexiv (a ≡ a), symmetrisch (a ≡ b ⇒ b ≡ a) und transitiv (a ≡ b ∧ b ≡ c ⇒ a ≡ c) – eine Äquivalenzrelation.
Wie verhalten sich Kongruenzen bei Addition und Multiplikation?
Rückseite
Aus a ≡ b und c ≡ d folgt a + c ≡ b + d und a·c ≡ b·d (mod m) – Rechenregeln bleiben erhalten.
Was ist eine Restklasse modulo m?
Rückseite
Die Menge aller ganzen Zahlen, die modulo m kongruent zu einer gegebenen Zahl a sind: [a]_m = {a + k·m | k ∈ ℤ}.
Wie viele Restklassen gibt es modulo m?
Rückseite
Genau m verschiedene Restklassen: [0], [1], …, [m−1]. Sie bilden den Restklassenring ℤ/mℤ.
Wann existiert ein multiplikatives Inverses modulo m?
Rückseite
Eine Zahl a hat genau dann ein Inverses modulo m, wenn gcd(a, m) = 1 gilt – also a und m teilerfremd sind.
Wie berechnet man das modulare Inverse effizient?
Rückseite
Mit dem erweiterten euklidischen Algorithmus: Man bestimmt x, y mit a·x + m·y = gcd(a,m) = 1, dann ist x das Inverse.
Was besagt der chinesische Restsatz?
Rückseite
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.
Was besagt der kleine fermatsche Satz?
Rückseite
Für eine Primzahl p und a mit p ∤ a gilt a^(p−1) ≡ 1 (mod p). Grundlage für Primzahltests und Kryptographie.
Was ist die eulersche Phi-Funktion φ(n)?
Rückseite
φ(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).
Was besagt der eulersche Satz?
Rückseite
Für teilerfremde a, n gilt a^φ(n) ≡ 1 (mod n). Verallgemeinert den kleinen fermatschen Satz auf beliebige Moduln.
Wie funktioniert modulare Exponentiation mit Square-and-Multiply?
Rückseite
Man zerlegt den Exponenten binär, quadriert die Basis wiederholt modulo m und multipliziert nur bei gesetzten Bits – Laufzeit O(log e).
Was ist ein quadratischer Rest modulo p?
Rückseite
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.
Was besagt der Satz von Wilson?
Rückseite
Eine Zahl p > 1 ist genau dann prim, wenn (p−1)! ≡ −1 (mod p) gilt. Theoretisch wichtig, praktisch ineffizient für Primzahltests.
Welche Rolle spielt modulare Arithmetik im RSA-Verfahren?
Rückseite
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)).