Cryptography Reference
In-Depth Information
mit
v
2
Berechne gegebenenfalls
v
∈
F
=
σ
(
u
)
.
(
u
,
±
v
)
sind zwei Punkte der Kurve.
Bemerkung
Lemma 11.1 zeigt, wie der zweite Schritt durchgeführt werden kann. Dieses Lem-
ma gilt für beliebige endliche Körper ungerader Ordnung. Der Beweis kann fast
wörtlich übernommen werden. Zum dritten Schritt, speziell für die Körper
Z
p
siehe Abschnitt 9.3.2, insbesondere die Bemerkung auf Seite 175.
14.4.2 Zur Existenz elliptischer Kurven mit vorgegebener Ordnung
Wir benutzen
t
weiterhin in seiner Bedeutung aus dem Satz 14.1 von Hasse. Eine
elliptische Kurve
E
über dem endlichen Körper
|
F
|
=
p
ν
,
p
prim, heißt
supersingulär
, wenn
p
ein Teiler von
t
ist. Man beachte, dass die Kurve
E nicht
singulär ist! Insofern ist die Wahl des Begriffs etwas verwirrend.
Der folgende Satz besagt insbesondere, dass es außer im supersingulären Fall
(der für die Kryptologie nicht so interessant ist) zu jeder Ordnung im durch den
Satz von Hasse gegebenen Intervall auch tatsächlich eine elliptische Kurve gibt.
Nach [28] gilt:
F
mit
Satz 14.2
Über dem Körper
F
existiert eine elliptische Kurve mit
|E|
=
q
+
− t genau dann,
1
wenn eine der folgenden Bedingungen erfüllt ist
mod
p
)
und t
2
(i)
t
≡
0
(
≤
4
q (E ist also nicht supersingulär),
(ii)
2
m und t
=
0
,
| m und
(iii) 2
t
2
t
2
=
≡
(
)
=
q
,
p ≡
(
)
=
t
0,
p
1
mod 4
oder
1
mod 3
oder
4
q
.
Bemerkung
Ist
q
=
p
, also
F
=
Z
p
, so gibt es für jedes
2
√
p
,
p
+
2
√
p
]
∩
N
c ∈ I
=[
p
+
−
+
:
1
1
|E|
=
c
. Die Verteilung der Ordnun-
gen auf das Intervall
I
ist nahezu gleichmäßig, mit einem leichten Abfall an den
Rändern. Diese Tatsache ist für den Faktorisierungs-Algorithmus ECM von Len-
stra wichtig. Wenn man die Schranke
B
geeignet wählt, sodass es genügend
B
-
potenzglatte Zahlen in
I
gibt, dann findet man mit hoher Wahrscheinlichkeit eine
Kurve mit
B
-potenzglatter Ordnung. Diese Variabilität ist der große Vorteil von
ECM gegenüber der
p
−
mindestens eine elliptische Kurve
E
mit
1-Methode von Pollard.
