Cryptography Reference
In-Depth Information
2. Fall:
Es existiert kein
a
∈
G
mit
p
|
o
(
a
)
. Mit dem Satz von Lagrange folgt dann
∈
\{
}
(
(
)) =
für jedes
a
G
1
wegen ggT
p
,
o
a
1:
m
|
|
=
<
G
/
a
p
pm
.
)
∈
N
(
o
a
∈
(
)=
Nach Induktionsvoraussetzung existiert ein
b
a
G
/
a
mit
o
b
a
p
.
Das Element
b
a
ist das Bild von
b
∈
G
unter dem (kanonischen) Epimorphis-
→
→
mus
π
:
G
G
/
a
,
g
g
a
. Wegen der Homomorphie von
π
gilt:
b
o
(
b
)
o
(
b
)
(
π
(
b
))
=
π
=
π
(
1
)=
a
.
Da
a
das neutrale Element in
G
/
a
ist, folgt mit (iii) in Lemma 6.1 (b) wegen
(
π
(
)) =
o
b
p
:
p
|
o
(
b
)
,
sodass dieser 2. Fall tatsächlich gar nicht eintreffen kann.
Beispiel
Weg
en
|
Z
8
|
=
|
Z
8
|
ϕ
(
)=
8
4 gilt
4. Es ist 2 der einzige Primteiler von
, und es
|
Z
8
|
sind 3, 5, 7 Elemente der Ordnung 2. Obwohl 4 ein Teiler von
ist, existiert
Z
8
der Ordnung 4; 4 ist keine Primzahl.
kein Element in
6.1.6 Die Sätze von Euler und Fermat
Wir ziehen aus dem Satz von Lagrange eine Reihe von wichtigen Schlüssen, die
fundamental für die Kryptologie sind.
Korollar 6.9
Ist G eine endliche Gruppe, so gilt für jedes a
∈
G:
a
|
G
|
=
(a)
1
(Satz von Euler).
gilt a
m
≡
(
|
|
)
=
(b)
Für m
1
mod
G
a.
∈
Beweis.
(a) Nach dem Satz von Lagrange ist die Ordnung von
a
G
ein Teiler
. Nach Lemma 6.1 (b) gilt
a
o
(
a
)
=
der Gruppenordnung
|
G
|
1, damit folgt die
Behauptung aus (iii) in Lemma 6.1 (b).
(b) Es sei
n
:
=
|
G
|
. Gilt
m
≡
1
(
mod
n
)
, so existiert ein
q
∈
Z
mit
m
−
1
=
nq
.Es
folgt
a
1
+
nq
a
m
a
n
q
=
=
(
)
=
a
a
denn
a
n
=
1, wie in Teil (a) gezeigt.
Ein wichtiger Spezialfall der Aussage in (b) ist der
(kleine) Satz von Fermat
:
