Menge der primen Restklassen
In mathbb{Z} 8 gibt es acht Klassen overline{0}, dots, overline{7} . Wer malnehmen und wieder rückgängig machen will, kann aber nur mit den Klassen arbeiten, die ein Inverses haben – das sind die Prime Restklassen|primen Restklassen overline{1}, overline{3}, overline{5}, overline{7} . Diese „guten“ Klassen fasst man zu einer eigenen Menge zusammen: der Menge der primen Restklassen . Darin kann man ohne Ausnahme malnehmen und „teilen“ – deshalb rechnen Verschlüsselungsverfahren wie RSA genau hier. Definition mathbb{Z} m^ = { overline{a} in mathbb{Z} m mid text{ggT}(a, m) = 1 } qquad text{(auch } R m^ text{)} Anzahl der Elemente: Das ist genau die Euler'sche Phi-Funktion : | mathbb{Z} m^ | = varphi(m) Gruppe: ( mathbb{Z} m^ , cdot) ist eine kommutative Gruppe : - abgeschlossen: Das Produkt zweier primer Restklassen ist wieder prim (wer mit m keinen Teiler gemeinsam hat, bekommt auch beim Malnehmen keinen dazu). - neutrales Element: overline{1} - Inverses: Jede Klasse hat eins – berechnet mit dem Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus . - Reihenfolge egal: overline{a} cdot overline{b} = overline{b} cdot overline{a} Sonderfall Primzahl: Ist m = p eine Primzahl, dann ist mathbb{Z} p^ = { overline{1}, overline{2}, dots, overline{p - 1} } und varphi(p) = p - 1 . Bestimme mathbb{Z} 8^ . 8 = 2^3 → prim sind die Klassen mit ungeradem Repräsentanten: mathbb{Z} 8^ = { overline{1}, overline{3}, overline{5}, overline{7} }, qquad varphi(8) = 4 Multiplikati
Worum geht's?
Formel mit Erklärung
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
