Cryptography Reference
In-Depth Information
sodass also
t
ein Teiler von
d
ist.
⇐
: Nach (i) ist
d
ein gemeinsamer Teiler von
a
und
b
. Wegen (ii) ist jeder gemei
n-
same Teiler
t
von
a
und
b
ein Teiler von
d
. Daher gilt
t
≤
d
.
Es ist also ggT
(
a
,
b
)
auch maximal bezüglich der Relation
|
und nicht nur bezüg-
≤
lich
. Eine weitere wichtige Folgerung ist:
Lemma 4.13
Teilt eine Primzahl p ein Produkt a b ganzer Zahlen a und b, so teilt p bereits einen der
Faktoren a oder b, d. h.:
p
|
ab
⇒
p
|
a oder p
|
b
.
Beweis.
Ist
p
ein Teiler von
b
, so sind wir fertig. Ist
p
kein Teiler von
b
, so gilt
ggT
(
)=
1, und nach dem Satz 4.10 zum euklidischen Algorithmus existieren
ganze Zahlen
x
und
y
mit
px
p
,
b
a
. Nach Voraus-
setzung teilt
p
beide Summanden der linken Seite. Nach Lemma 4.8 also auch d
ie
rechte Seite
a
.
+
by
=
1. Es folgt
apx
+
aby
=
Aus dieser Aussage kannman die Eindeutigkeitsaussage des
Fundamentalsatzes
der Arithmetik
ohne viel Mühe herleiten. Wir haben das als Aufgabe formuliert.
Satz 4.14
(Fundamentalsatz der Arithmetik)
Jede natürliche Zahl N
1
lässt sich - bis auf die Reihenfolge der Faktoren - auf ge-
nau eine Art und Weise als ein Produkt von Primzahlpotenzen schreiben, d. h., es gibt
Primzahlen p
1
,...,
p
r
und natürliche Zahlen
>
ν
1
,...,
ν
r
∈
N
mit:
r
i
=
1
p
ν
i
=
N
.
i
< ··· <
Sortiert man die Primzahlen der Reihe nach, d. h. setzt man
p
1
p
r
,so
spricht man von der
kanonischen Primfaktorzerlegung
der natürlichen Zahl
N
>
1.
4.2.3 Komplexitätsanalyse des euklidische Algorithmus *
Im folgenden Satz benutzen wir die Zahl
+
√
5
2
1
=
≈
<
γ
:
1.618 . . .
2,
die auch
goldener Schnitt
genannt wird. Es ist
γ
eine Nullstelle des Polynoms
x
2
−
−
x
1, daher gilt
+
γ
−
1
.
γ
=
1
Das werden wir im Folgenden benutzen. Wir verwenden die im vorigen Ab-
schnitt eingeführten Bezeichnungen.
