Cryptography Reference
In-Depth Information
Wir erhalten
1
=
770
·
(
−
160
)+
351
·
351 , d. h. 1
=
351
·
351 ,
somit ist 351 das Inverse zu 351 in
Z
770
.
4.3.4 Eulers
ϕ
-Funktion
Bisher hatten wir
n
ein
Ring. Das Nullelemen
t
0 ist gleichzeitig Einselement und damit invertierbar. Es
gilt also
>
1
angenommen. Aber natürlich ist auch
Z
1
=
{
0
}
Z
1
=
Z
1
=
{
}
.
Für jede natürliche Zahl
n
bezeichnet man mit
0
Z
n
:
ϕ
(
n
)
die Mächtigkeit von
Z
n
ϕ
(
)=
n
.
N
→
N
Damit ist eine Abbildung
ϕ
:
erklärt - die
Euler'sche
ϕ
-Funktion
.
ϕ
(
)
Die Zahl
n
gibt wegen
Z
n
=
{
∈
Z
n
; ggT
(
)=
a
a
,
n
1
}
.
die Anzahl der natürlichen Zahlen aus
{
1,...,
n
}
an, die zu
n
teilerfremd sind.
Beispiel
ϕ
(
1
)=
1,
ϕ
(
2
)=
1,
ϕ
(
3
)=
2,
ϕ
(
4
)=
2,
ϕ
(
5
)=
4,
ϕ
(
6
)=
2,
ϕ
(
7
)=
6.
ϕ
(
)=
−
p
p
1 für jede Primzahl
p
(man vergleiche das mit Satz 4.17).
Für jede Primzahlpotenz
p
k
,
k
∈
N
, findet man:
p
k
1
,
1
p
p
k
−
1
p
k
p
k
ϕ
(
)=
−
=
−
da unter den
p
k
Zahlen 1, 2, . . . ,
p
k
genau die
p
k
−
1
Zahlen
p
,2
p
,...,
p
k
−
1
p
einen gemeinsamen Teiler mit
p
k
haben. Alle anderen Zahlen zwischen 1 und
p
k
, das sind
p
k
p
k
−
1
Zahlen, sind zu
p
k
teilerfremd.
−
für verschiedene Primzahlen
p
und
q
, da unter den
Zahlen 1, . . . ,
p
,..., 2
p
,...,
qp
genau
q
Zahlen einen gemeinsamen Teiler mit
p
haben und analog genau
p
Zahlen unter 1, . . . ,
q
,..., 2
q
,...,
pq
einen ge-
meinsamen Teiler mit
q
haben. Folglich sind genau
ϕ
(
pq
)=(
p
−
1
)(
q
−
1
)
pq
−
p
−
q
+
1
=(
p
−
1
)(
q
−
1
)
Zahlen unter 1, . . . ,
pq
zu
pq
teilerfremd. Der Summand 1 rührt daher, dass
wir die Zahl
pq
nur einmal berücksichtigen dürfen.
Auf weitere interessante Eigenschaften der Euler'schen
ϕ
-Funktion gehen wir in
Kapitel 7 ein.
