Cryptography Reference
In-Depth Information
Wir zeigen nun noch
.
|
|
+
G
k
|
|
=
T
k
+
1
Hieraus folgt dann die Behauptung in (iii). Dazu ordnen wir jeder
(
k
+
1
)
-
{
x
0
,
x
1
,...,
x
k
}
{
|
|
+
}
elementigen Teilmenge
von
1, . . . ,
G
k
(wobei wir ohne Ein-
schränkung
x
0
<
x
1
< ··· <
x
k
setzen) ein Tupel
(
e
0
,
e
1
,...,
e
k
)
zu, indem wir
die
e
i
aus den folgenden Gleichungen gewinnen:
+
=
+
+
=
+
+
···
+
e
k
+
+
=
e
0
1
x
0
,
e
0
e
1
2
x
1
,...,
e
0
e
1
k
1
x
k
.
≤|
|
+
(
+
)
(
)
Da
x
k
G
k
, liegt das
k
1
-Tupel
e
0
,
e
1
,...,
e
k
in der Menge
T
. Damit
haben wir eine Abbildung von der Menge aller
(
k
+
1
)
-elementigen Teilmengen
{
|
|
+
}
von
in
T
erklärt. Diese Abbildung ist offenbar bijektiv. Folglich
sind die beiden Mengen
P
und
T
gleichmächtig und (iii) ist begründet.
Als Nächstes begründen wir:
1, . . . ,
G
k
n
√
|
G
|
.
In der folgenden Ungleichungskette
bea
chte man der Reihe nach die Ungleichun-
gen bzw. Gleichungen
|
| >
(iv)
H
|
+
a
b
+
b
a
|
G
|≥
G
|
+
1 (siehe (ii)),
(
b
)=(
a
)
für alle
(siehe (ii)),
|
2
a
+
1
für alle
a
2
a
+
1
a
a
,
b
∈
N
,
k
≥
G
|
(
)
>
∈
N
>
1
(siehe Aufga-
be 8.7) und schließlich
=
log
2
n
+
1:
⎛
⎞
|
G
|
+
1
+
k
(
)
iii
|
|
+
|
|
+
+
G
k
G
1
k
⎝
⎠
|
H
|
≥
≥
=
|
+
k
1
k
+
1
G
|
⎛
2
⎞
2
√
|
G
|
+
1
2
√
|
G
|
=(
√
|
G
|
|
G
|
+
1
⎝
⎠
>
2
)
≥
≥
|
G
|
√
|
G
|
≥
(
√
|
G
|
=
n
√
|
G
|
.
2
log
2
n
+
1
2
log
2
n
=(
)
)
Damit ist (iv) begründet. Schließlich zeigen wir:
(v)
Die Zahl n besitzt außer p keine weiteren Primteiler.
An
gen
ommen,
n
besitzt einen weiteren Primteiler. Wir zeigen, dass dann
|
H
|≤
n
√
|
G
|
. Dazu betrachten wir die Menge
p
s
n
p
.
t
J
:
=
≤
≤
|
|
;0
s
,
t
G
Da
n
keine Potenz von
p
ist, gilt
p
s
p
t
p
s
p
t
, falls
s
,
t
)
=
(
s
,
t
)
=(
, sodass
1
2
J
|
=
|
|
|
+
> |
|
G
G
.
