Asymmetrische Verschlüsselung - Kryptografie - page 182

weiteres Element der Gruppe erhält (Abgeschlossenheit). Die Verknüpfung
muss zudem assoziativ sein, was bei der Modulo-Multiplikation gegeben ist.

■ Es gibt ein neutrales Element (in diesem Fall die Zahl 1). Ein neutrales Ele-

ment hat die Eigenschaft, dass man bei der Verknüpfung mit einem anderen
Element dieses andere Element als Ergebnis erhält.

■ Zu jedem Element gibt es ein inverses Element. Da p eine Primzahl ist, ist

diese Voraussetzung in unserem Fall gegeben.

Beachten Sie, dass p auch wirklich eine Primzahl sein muss, ansonsten haben
nicht alle Elemente ein inverses Element, und es handelt sich dann nicht um eine
Gruppe. Außerdem gehört die Null nicht zur Gruppe Z( p ,·), da die Null kein
inverses Element besitzt. Übrigens ist die Menge der Zahlen zwischen 0 und p -1
auch bezüglich der Modulo-Addition eine Gruppe - wir nennen sie Z( ,+) . Dieses

p

Mal ist die Null Bestandteil der Gruppe (sie ist das neutrale Element).
Die Menge der Zahlen zwischen 0 und p -1 bilden damit sowohl mit der
Modulo-Addition als auch mit der Modulo-Multiplikation (ohne die Null) eine
Gruppe. Eine solche »Doppelgruppe« wird in der Mathematik Körper genannt.
Einen Körper, der auf die beschriebene Weise aus den Zahlen 0 bis p -1 entsteht,
nennt man Körper der Größe p oder Galois-Feld der Größe p . Wir schreiben
dafür GF(

) .

p

Untergruppen

Eine Untergruppe ist eine Teilmenge einer Gruppe, die (mit derselben Verknüp-
fung und demselben neutralen Element) selbst wieder eine Gruppe bildet. Nicht
jede Teilmenge einer Gruppe ist automatisch eine Untergruppe. Eine Minimalan-
forderung ist, dass das neutrale Element in der Teilmenge enthalten ist. Darüber
hinaus fehlt bei vielen Teilmengen die Abgeschlossenheit - dies bedeutet, dass bei
der Verknüpfung zweier Elemente der Teilmenge das Ergebnis nicht zur Teil-
menge gehört.

Beispiel: Betrachten wir Z(5,·), dann gilt:
■

{2, 3} ist keine Untergruppe, da das neutrale Element fehlt.

■ {1, 3} ist keine Untergruppe, da gilt: 3·3=4 (mod 5). 4 ist jedoch kein Element

der Teilmenge.

■ {1, 4} ist eine Untergruppe, da gilt: 1·1=1 (mod 5), 1·4=4 (mod 5),

4·1=4 (mod 5) und 4·4=1 (mod 5). Abgeschlossenheit ist also gegeben, da bei
allen möglichen Verknüpfungen stets ein Element der Teilmenge entsteht.

Man kann beweisen, dass die Anzahl der Elemente in einer Untergruppe ein Tei-
ler der Anzahl der Elemente der zugehörigen Gruppe ist. Da die Gruppe Z( p ,·)
genau p -1 Elemente besitzt, bedeutet dies, dass die Anzahl der Elemente in einer
Untergruppe stets p -1 teilt. Hier ein Beispiel: Die Gruppe Z(13,·) hat 12 Ele-
mente. Die Untergruppen von Z(13,·) haben daher 1, 2, 3, 4, 6 oder 12 Elemente.