Cryptography Reference
In-Depth Information
und
b
. Umgekehrt findet man in jedem Integritätsring zu je zwei größten gemeinsamen
Teilern
c
und
d
jeweils eine Einheit
e
, so dass
c
=
ed
gilt. Mit anderen Worten:
Lemma 3.5.2.
Es sei
R
ein Integritätsring,
a, b ∈ R
und
c ∈ R
ein größter gemeinsamer
Teiler von
a
und
b
.Dannist
R
∗
}
{
ce
|
e
∈
die Menge aller größten gemeinsamen Teil
er
von
a
und
b
.
der ganzen Zahlen gibt es zu je zwei Zahlen
a
und
b
einen größten gemein-
samen Teiler. Da
1
und
Im Ring
Z
ein Integritätsring
ist, folgt mit Lemma 3.5.2, dass es genau zwei größte gemeinsame Teiler von
a
und
b
gibt,
etwa
d
und
d
, und dass für diese
d
=
−
1
die einzigen Einheiten von
Z
sind und
Z
d
gilt. Es sei denn, es gilt
a
=
b
=0
.Indiesem
Fall ist
0
der einzige größte gemeinsame Teiler. Für
−
trifft man die Vereinbarung, dass
ggT
(
a, b
)
der nicht-negative größte gemeinsame Teiler von
a
und
b
ist.
Zwei ganze Zahlen
a
und
b
heißen
teilerfremd
, falls ggT
(
a, b
)=1
gilt. Für
a
Z
∈
Z
n
gilt:
i)
a
=0
genau dann, wenn ggT
(
a, n
)=
n
.
ii)
a ∈
Z
n
(d. h.
a
ist eine Einheit) genau dann, wenn ggT
(
a, n
)=1
.
iii)
a
ist ein Nullteiler in
Z
n
genau dann, wenn
1
<
ggT
(
a, n
)
<n
.
Daraus folgt sofort, dass
(mit Multiplikation modulo
n
) genau dann eine Gruppe
ist, wenn
n
eine Primzahl ist. Insbesondere ist
Z
n
\{
0
}
Z
n
(mit Addition und Multiplikation
modulo
n
) ein Körper genau dann, wenn
n
eine Primzahl ist.
Über die Anzahl der Elemente von
Z
n
lässt sich Folgendes festhalten.
...p
α
r−
1
r−
1
2
mit
n
=
p
α
0
0
Satz 3.5.1 (Eulersche
φ
-Funktion).
Es sei
n
für paarweise
verschiedene Primzahlen
p
i
und von Null verschiedene natürliche Zahlen
α
i
. Die Anzahl
der Elemente von
≥
Z
n
ist
...
(
p
r−
1
−
1)
p
α
r−
1
−
1
φ
(
n
)=(
p
0
−
1)
p
α
0
−
1
.
(3.5.1)
0
r−
1
Die Funktion
φ
:
{
2
,
3
,
4
,...
}→
N
wird
Eulersche
φ
-Funktion
genannt.
Beim algorithmischen Umgang mit Restklassenringen stellen sich häufig die beiden
folgenden Probleme:
1. Berechne zu
a, b
∈
Z
die Zahl ggT
(
a, b
)
. Damit läßt sich insbesondere feststellen, ob
Z
n
gehört.
2. Berechne zu gegebenem Element
a
ein Element von
Z
n
zu
∈
Z
n
sein multiplikatives Inverses.
Beide Probleme können ezient mit Hilfe des erweiterten Euklidschen Algorithmus gelöst
werden. Dazu halten wir zunächst folgenden Satz fest:
Satz 3.5.2 (erweiterter Euklidscher Algorithmus).
Algorithmus 3.1 ist bezüglich Vor-
und Nachbedingung korrekt und terminiert nach höchstens
log
a
Schleifendurchläufen,
wenn die Vorbedingung erfüllt ist. Außerdem sind alle auftretenden Zahlen betragsm
ä
-
ßig durch
a
beschränkt.
Die Korrektheit des Algorithmus ergibt sich - wie in der Beschreibung des Algorithmus
angedeutet - aus ggT
(
a, b
)=
ggT
(
b, a
mod
b
)
, was für alle
a, b
mit
b>
0
gilt. Aus den
im Satz angegebenen Schranken für die Anzahl der Schleifendurchläufe und die Größe der
auftretenden Zahlen lässt sich leicht ableiten, dass der erweiterte Euklidsche Algorithmus
∈
Z
