Dies ist eine alte Version des Dokuments!


Kongruenz und Restklassen

tm.jpg

Kongruenz

Wir betrachten die Reste, die bei der Ganzzahldivision auftreten, z.B.:

12 : 7 = 1, 5 R 
24 : 5 = 4, 4 R
...

Wir sagen:

tex:12 \equiv 5 (mod 7)
tex:24 \equiv 4 (mod 5)

Da

24 : 5 = 4, 4 R 
9 : 5 = 1, 4 R

gilt, und da offensichtlich die Zahl 24 als auch die Zahl 9 bei der Division durch die gleiche Zahl 5 den gleichen Rest 4 liefern, heißen die beiden Zahlen 24 und 9 (und unendlich viele weitere) kongruent bezüglich des Moduls 5:

tex:24 \equiv 9 (mod 5)

Rechenregeln für Kongruenzen

Für ganze Zahlen tex:m \ne 0, a, b, c, tex:c \equiv a (mod m), d, tex:d \equiv b (mod m), k, gelten folgende Rechenregeln:

tex:k \cdot a \equiv k c (mod m)
tex:a \pm b \equiv c \pm d (mod m)
tex:a \cdot b \equiv c \cdot d (mod m)

Überprüfe im folgenden GeoGebra-Applet die Rechengesetze für die Addition und Multiplikation (mod m):

Screenshot: Alfred Nussbaumer

Download der GeoGebra-Datei

Zyklische Gruppen

Zyklische Gruppen bestehen aus allen Potenzen eines einzelnen Elements g. g heißt das erzeugende Element.

Wir betrachten besondere Restklassengruppen, nämlich solche, deren Modul m eine Primzahl p ist.

Beispiele für zyklische Gruppen

Z7 = {0,1,2,3,4,5,6}, Z7* = {1,2,3,4,5,6}
Z11 = {0,1,2,3,4,5,6,7,8,9,10}, Z11* = {1,2,3,4,5,6,7,8,9,10}

Eine zyklische Gruppe Zp, p eine Primzahl, hat p - 1 Elemente; ihre erzeugenden Elemente heißen Primitivwurzeln

Beispiel: Erzeugendes Element, Primitivwurzel

2 ist kein erzeugendes Element von Z7*:

tex:2^2 = 4, tex:2^3 = 8 \equiv 1, tex:2^4 = 16 \equiv 2, tex:2^5 = 32 \equiv 4, tex:2^6 = 64 \equiv 1 mod 7

3 ist ein erzeugendes Element von Z7:

tex:3^2 = 9 \equiv 2, tex:3^3 = 27 \equiv 6, tex:3^4 = 3^2 \cdot 3^2 \equiv 2 \cdot 2 = 4tex:3^5 = 3^3 \cdot 3^2 \equiv 6 \cdot 2 = 12 \equiv 5, tex:3^6 = 3^3 \cdot 3^3 \equiv 6 \cdot 6 = 36 \equiv 1 mod 7

Eine zyklische Gruppe kann mehrere verschiedene erzeugende Elemente haben, z.B. ist auch 5 ein erzeugendes Element für Z7*

Aufgaben:

Suche erzeugende Elemente für zyklische Gruppen bis p = 17 mit dem folgenden GeoGebra-Applet. Wähle zunächst die Primzahl p und teste anschließend für verschiedene Elemente g, ob sie Primitivwurzeln sind!

Screenshot: Alfred Nussbaumer

Download der GeoGebra-Datei

  • Gib alle erzeugenden Elemente für eine gewählte zyklische Gruppe an!
  • Sobald sich ein Ergebnis in der Potenzreihe wiederholt, kann g kein erzeugendes Element sein. Begründe!

Zurück zu Lernpfad Kryptographie | GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...