Cryptography Reference
In-Depth Information
14.3.2 Die Idee
Wie bei Pollards
p
−
1-Methode betrachten wir die Gruppenordnung von
E
p
mit
einem unbekannten Primteiler
p
von
N
. Wenn diese
B
-potenzglatt für ein vorher
festgelegtes
B
∈
N
ist, so kannman wie folgt vorgehen: Setze wie schonmehrfach
geschehen
λ
(
B
)
:
=
kgV
(
1, . . . ,
B
)
;
dann gilt für jeden Punkt
P ∈ E
aff
, dass
η
p
(
λ
(
B
)
P
)=
O
in
E
p
, aber nicht not-
wendig
in
E
.
Wenn dieser Fall eintritt, findet man einen nichttrivialen Teiler von
N
wie am
Ende des letzten Abschnitts beschrieben.
Falls der seltene Fall eintritt, dass
λ
(
B
)
P
=
O
in
E
(gewissermaßen simultan für
alle Primteiler von
N
), könnte man mit einem anderen Punkt starten oder eine
neue Kurve wählen.
Leider ist es imAllgemeinen nicht leicht, Punkte auf elliptischen Kurven über
λ
(
B
)
P
=
O
Z
N
zu finden, wenn
N
keine Primzahl ist. Es sind hierzu nämlich Quadratwurzeln
modulo
N
zu ziehen, und Lemma 9.3 besagt, dass das Ziehen von Quadratwur-
zeln modulo
N
mindestens so schwer ist wie das Faktorisieren von
N
. Deshalb
geht man in der Praxis den zweiten Weg: Man wählt eine neue Kurve.
14.3.3 Der Algorithmus ECM
(
6,
N
)=
Wir dürfen ohne Einschränkung annehmen, dass ggT
1 ist. Dann existie-
ren elliptische Kurven über
Z
N
wie im vorigen Abschnitt beschrieben, und die
Formeln für die Addition können wie oben angewendet werden.
Tatsächlich wählt man Kurven spezieller Gestalt, nämlich solche mit affiner Glei-
chung
y
2
=
x
3
+
ax
+
1.
Man kann dann
P
=(
wählen, und hat das Problem, einen Punkt
auf
E
finden zu müssen, schon gelöst. Ein anderer Weg, eine Kurve mit einem
bekannten Punkt zu finden, wird in der Aufgabe 14.3 angedeutet.
Weiter muss die Schranke
B
gewählt werden. Die Wahl hängt davon ab, wie lange
man suchen will. Wir werden später sehen, dass die Größe von
B
auch Einfluss
auf die Größe der Teiler von
N
, die man finden kann, hat.
Es seien
p
1
,...,
p
k
alle Primzahlen kleiner gleich
B
, am Besten beginnend mit
p
1
0:1:1
)
maximal mit
p
ν
i
i
=
ν
i
∈
N
≤ B
für alle
2 der Größe nach geordnet. Wähle
i
∈{
1, . . . ,
k
}
.
Zunächst muss durch Primzahltests sichergestellt werden, dass
N
keine Prim-
zahl ist; sonst - Stop!
Lege die Schranke
B
fest.