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.
Search WWH ::




Custom Search