Cryptography Reference
In-Depth Information
14.3 Faktorisierung mit elliptischen Kurven
Im Jahre 1987 schlug H. W. Lenstra vor, elliptische Kurve zur Faktorisierung na-
türlicher Zahlen zu nutzen. Lenstras Verfahren wird meist mit ECM (
Elliptic Cur-
ve Method
) bezeichnet.
Bei Lenstras Verfahren rechnet man in einer Menge
G
mit einer nicht wohldefi-
nierten Verknüpfung. Die Menge
G
wäre mit dieser Verknüpfung eine Gruppe,
wenn die zu faktorisierende Zahl
N
eine Primzahl wäre. Gerade die Tatsache,
dass der Versuch, Elemente aus
G
zu verknüpfen scheitern kann, führt zu nicht-
trivialen Faktoren von
N
.
Gegeben sei also eine natürliche Zahl
N
, die es zu faktorisieren gilt. Genauer
suchen wir nach einem nichttrivialen Teiler
d
von
N
. Gegebenenfalls wäre das
Verfahren auf
d
und
d
erneut anzuwenden.
Z
N
14.3.1 Elliptische Kurven über dem Ring
(
6,
N
)=
Ohne Einschränkung dürfen wir voraussetzen, dass ggT
1 ist. Es sei
p
ein
- uns unbekannter - Primteiler von
N
. In einer elliptischen Kurven
E
über dem
Körper
Z
p
können wir nicht rechnen, da uns
p
nicht bekannt ist. Wir werden
daher in
E
modulo
N
rechnen,
E
also als Kurve über dem Ring
Z
N
auffassen.
Wie schon mehrfach geschehen, identifizieren wir Restklassen modulo
N
gele-
gentlich mit ihren kleinsten nichtnegativen Repräsentanten.
=
(
x
,
y
,
z
)
∈
Z
1
. In Analogie zur Konstrukti-
3
Es sei
V
:
(
x
,
y
,
z
,
N
) =
N
; ggT
on der Punktmenge von PG
(
2,
Z
p
)
definieren wir eine Äquivalenzrelation auf
V
durch
⇔∃λ ∈
Z
N
:
(
x
1
,
y
1
,
z
1
)
∼
(
x
2
,
y
2
,
z
2
)
(
x
1
,
y
1
,
z
1
) =
λ
(
x
2
,
y
2
,
z
2
)
:
P
=
V
/
∼
und bezeichnen die Menge aller Äquivalenzklassen
:
als die Punktmen-
Z
N
. Für die Äquivalenzklasse des Punktes
(
x
,
y
,
z
)
ge der projektive Ebene über
schreiben wir wie gehabt
(
x
:
y
:
z
)
.
Weil
Z
N
kein Körper ist, kann man nicht ohne Weiteres Geraden einführen. Wir
betrachten daher nur die
Punktmenge
.
I
n An
alo
gie zu unserer Darstellung in Kapitel 13 setzen wir für
a
,
b ∈
Z
N
mit
4
a
3
∈
Z
N
27
b
2
+
=
Y
2
Z − X
3
+
aXZ
2
+
bZ
3
(
X
,
Y
,
Z
)
∈
Z
N
[
X
,
Y
,
Z
]
F
:
und erklären die
elliptische Kurve
über
Z
N
durch
=
{
(
u
:
v
:
w
)
∈P
;
F
(
u
,
v
,
w
)=
E
:
0
}
.
Wie in Abschnitt 13.2.1 erkennt man, dass
E
wohldefiniert ist.
