Cryptography Reference
In-Depth Information
Aufgaben
=
=
−
11.1
Warum sollten bei Pollards
-Methode die Koeffizienten
c
0 und
c
2
x
2
für
f
(
x
)=
+
c
zur rekursiven Konstruktion der Folge
(
x
i
)
vermieden werden?
11.2
Implementieren Sie Pollards
-Methode.
11.3
Bestimmen Sie alle Primzahlen
p
, sodass
p
−
1
5 -potenzglatt ist.
11.4
Es sei
N
eine natürliche Zahl m
it
mindestens zwei verschiedenen Primtei-
le
r.
Da
n
n existieren zu jedem Quadrat
x
2
in
Z
N
mindestens vier Quadratwurzeln
∈
Z
N
, wobei 1
±
±
<
(
−
)
<
x
,
y
ggT
x
y
,
N
N
.
Hinweis:
Betrachten Sie die Beweise
zu den Lemmata 9.1 und 9.3.
11.5
Beweisen Sie Korollar 11.4.
11.6
Bestimmen Sie mit den Daten aus dem Beispiel auf Seite 206 die Faktori-
sierung der Zahl
N
=
589, indem Sie das Verfahren aus Abschnitt 11.4.3 durch-
führen.
11.7
Zerlegen Sie 5 609 mit jedem der angegeben Verfahren.