Cryptography Reference
In-Depth Information
7.2.3 Produktdarstellung der primen Restklassengruppen
Für die Abbildung
ψ
aus Lemma 7.3 und
r
:
=
r
1
···
r
n
gilt
Z
)
∈
Z
r
1
×···×
Z
r
n
⇔
ψ
(
k
+
r
ggT
(
k
,
r
i
)=
1 für
i
=
1, . . . ,
n
Z
∈
Z
r
⇔
ggT
(
k
,
r
)=
1
⇔
k
+
r
.
Z
r
Somit ist die Einschränkung
ψ
|
Z
r
auf die (multiplikative) Gruppe
der inver-
tierbaren Elemente von
Z
r
wegen Lemma 7.3 ein Gruppenisomorphismus von
Z
r
Z
r
1
×···×
Z
r
n
:
auf
Lemma 7.5
(a) Für paarweise teilerfremde r
1
,...,
r
n
und r
:
=
r
1
···
r
n
ist
ψ
|
Z
r
:
k
+
r
1
···
r
n
Z
→
(
k
+
r
1
Z
,...,
k
+
r
n
Z
)
Z
r
1
···
r
n
auf
Z
r
1
×···×
Z
r
n
.
ein (multiplikativer) Isomorphismus von
p
ν
1
p
ν
n
die kanonische Primfaktorzerlegung von m
=
···
>
(b) Ist m
1
aus
N
, so gilt
Z
m
=
Z
p
ν
1
×···×
Z
p
ν
n
.
∈
N
≥
2
als Produkt
Nach dem Fundamentalsatz 4.14 der Arithmetik kann jedes
m
von Primzahlpotenzen dargestellt werden:
p
ν
1
p
ν
n
m
=
···
.
Wegen Lemma 4.16 folgt für die Euler'sche
ϕ
-Funktion (siehe Seite 75):
1
1
.
n
i
=
1
|
Z
p
ν
i
|
=
n
i
=
1
ϕ
(
p
ν
i
n
i
=
1
p
ν
i
n
i
=
1
1
p
i
1
p
i
)=
|
Z
m
|
=
ϕ
(
m
)=
−
=
m
−
i
i
Wir fassen zusammen:
Lemma 7.6
(a) Für paarweise teilerfremde s
1
,...,
s
n
∈
N
gilt
ϕ
(
s
1
···
s
n
)=
ϕ
(
s
1
)
···
ϕ
(
s
n
)
.
>
(b) Sind p
1
,...,
p
n
die verschiedenen Primteiler von m
1
aus
N
,soist
m
1
1
.
1
p
1
1
p
n
ϕ
(
m
)=
−
···
−
Beispiel
Es gilt etwa
1
2
·
2
3
·
4
5
·
6
7
=
ϕ
(
33
)=
ϕ
(
3
)
ϕ
(
11
)=
20 ,
ϕ
(
420
)=
420
·
96 .
