Cryptography Reference
In-Depth Information
Man kann außerdem zeigen, dass es zu Z(
p
,·) für jeden Teiler von
p
-1 genau eine
Untergruppe mit dieser Anzahl von Elementen gibt. Hier ein Beispiel: Zu Z(13,·)
gibt es jeweils eine Untergruppe mit 1, 2, 3, 4, 6 und 12 Elementen. Die Unter-
gruppe mit 12 Elementen ist die Gruppe selbst. Die Untergruppe mit einem Ele-
ment enthält nur die Zahl 1.
Generatoren
Eine weitere Aussage, die sich beweisen lässt: Nimmt man ein beliebiges Element
a
aus Z(
p
,·) und betrachtet die Menge {
a
,
a
2
,
a
3
,
a
4
, ...,
a
p-1
(mod
p
)}, dann erhält
man eine Untergruppe.
a
heißt
Generator
der Untergruppe. Jede Untergruppe von
Z(
p
,·) hat mindestens einen Generator, und damit auch Z(
p
,·) selbst. Die folgende
Tabelle zeigt die Untergruppen von Z(13,·):
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
a
11
a
12
a
1
2
4
8
3
6
12
11
9
5
10
7
1
3
9
1
4
3
12
9
10
1
5
12
8
1
6
10
8
9
2
12
7
3
5
4
11
1
7
10
5
9
11
12
6
3
8
4
2
1
8
12
5
1
9
3
1
10
9
12
3
4
1
11
4
5
3
7
12
2
9
8
10
6
1
12
1
Aus der Tabelle lässt sich beispielsweise herauslesen, dass die Zahl 1 der einzige
Generator der Untergruppe von Z(13,·) mit einem Element ist. Die Untergruppe
mit zwei Elementen hat den Generator 12. Für die Untergruppe mit drei Elemen-
ten gibt es zwei Generatoren: 3 und 9. Die Zahlen 5 und 8 generieren die Unter-
gruppe mit vier Elementen. Die Untergruppe mit sechs Elementen wird von 4 und
10 generiert. 2, 6, 7 und 11 sind Generatoren der Untergruppe mit 12 Elementen,
also Z(13,·) selbst.
Dass es auch Generatoren für Z(
p
,·) selbst gibt, spielt in der Kryptografie eine
wichtige Rolle. Wie Sie leicht nachvollziehen können, ist die Gleichung
a
x
=
b
(mod
p
) immer lösbar, wenn
a
ein Generator von Z(
p
,·) ist (
b
ist dabei ein Ele-
ment von Z(
p
,·) und darf daher nicht Null sein). Mit anderen Worten heißt dies:
Der diskrete Logarithmus in Z(
p
,·) existiert immer, wenn die Basis ein Generator
von Z(
p
,·) ist.
