Cryptography Reference
In-Depth Information
a
2
N
X
2
N
Beweis.
Für ein
N
∈
N
betrachten wir das Polynom
f
=
+
···
+
a
1
X
+
a
0
X
0
∈
Z
[
]
X
. Es gilt
1
i
=
0
a
i
1
2
N
2
N
i
=
0
a
i
m
t
i
d
t
f
(
t
)
d
t
=
=
1
=
für ein
m
∈
Z
.
+
λ
(
+
)
i
2
N
1
0
0
X
N
N
, das eine sol-
=
(
−
)
Nun betrachten wir das spezielle Polynom
f
1
X
che betrachtete Form hat. Es gilt für alle 0
<
t
<
1 die Ungleichungskette
1
<
(
)
≤
0
f
t
4
N
- für die Abschätzung nach oben zeige man, dass die Polynom-
N
auf dem Intervall
funktion
f
(
x
)=(
x
(
1
−
x
))
[
0, 1
]
ein globales Maximum in
=
x
1/2 besitzt. Es folgt
1
m
1
4
N
0
<
f
(
t
)
d
t
=
)
≤
λ
(
+
2
N
1
0
für ein
m
∈
N
. Das liefert
2
(
2
N
+
1
)
−
2
,
4
N
λ
(
+
)
≥
≥
2
N
1
=
+
also die Behauptung für ungerade
n
2
N
1. Wegen
4
N
2
(
2
N
+
2
)
−
2
λ
(
2
N
+
2
)
≥
λ
(
2
N
+
1
)
≥
=
=
+
folgt die Behauptung auch für gerade
n
2
N
2.
Mit diesem Lemma können wir nun zeigen, dass es ein
r
der gewünschten Grö-
ßenordnung gibt.
Lemma 8.12
Zu n
5
∈
N
>
1
der Länge
=
log
2
n
+
1
mit
ggT
(
n
,
λ
(
)) =
1
existiert ein r
∈
N
5
und o
2
.
≤
(
)
mod
r
>
mit r
n
2
für
Beweis.
Wir nehmen an, dass kein solches
r
existiert. Dann gilt
o
(
n
)
mod
r
≤
5
, denn
r
und
n
sind nach Voraussetzung teilerfremd. Das besagt, dass
≤
jedes
r
5
eine Kongruenz der Form
n
i
2
für jedes
r
≤
≡
1
(
mod
r
)
für ein
i
∈{
1, . . . ,
}
5
:
≤
gilt. Damit erhalten wir für jedes
r
2
i
=
1
(
n
i
2
i
=
1
(
n
i
5
|
−
)
λ
(
)
|
−
)
r
1
und damit
1
.
5
2
−
2
gilt; wir erhalten:
5
Wir wenden nun Lemma 8.11 an, wonach
λ
(
)
≥
2
log
2
(
n
)
2
i
=
1
(
n
i
2
i
=
1
n
i
2
2
(
+
)
1
/2
5
2
2
3
2
2
−
2
n
(
+
1
)
/2
2
(
+
1
)
/2
.
≤
−
1
)
<
=
=
≤
