Cryptography Reference
In-Depth Information
4
a
3
Wähle
a
∈
N
und bestimme
d
:
=
ggT
(
+
27,
N
)
.
Falls
d
=
1 weiter mit dem nächsten Schritt;
falls
d
=
N
, wähle neues
a
;
sonst Teiler
d
von
N
gefunden - Stop!
Auf der Kurve
E
:
y
2
=
x
3
+
ax
+
1, setze
P
0
=(
0:1:1
)
, und bestimme
=
p
ν
i
i
P
i−
1
mit
i
=
rekursiv
P
i
:
1, . . . ,
k
, soweit möglich.
Falls
P
k
existiert, d. h. bei der Rechnung nichts schief geht, wähle ein neues
a
wie im vorigen Schritt und wiederhole;
(
∗
)
falls nicht, ist ein Nenner
r
aus der Berechung von
α
in
nicht invertierbar
modulo
N
;
Bestimme
d
:
=
ggT
(
r
,
N
)
falls
d
=
N
, wähle ein neues
a
wie im ersten Schritt;
sonst ist
d
der gesuchte Teiler - Stop!
Wenn wir den seltenen Fall
P
k
=
O
ausblenden, so liefert der Algorithmus immer
dann einen Teiler von
N
, wenn es einen Primteiler
p
von
N
gibt, für den die Kurve
E
p
eine Mächtigkeit hat, die
B
-potenzglatt ist. In diesem Fall ist
E
p
ein Teiler von
λ
(
B
)
und daher gilt
η
p
(
P
k
)=
η
p
(
λ
(
B
)
P
)=
O
in
E
p
.
Bemerkung
Die Laufzeit der ECM ist
O
exp
log
N
log log
N
, wenn für den kleinsten
Primteiler
p
von
N
gilt
exp
1
.
B
≈
2
log
p
log log
p
Die Wahl der Schranke wird tatsächlich an der Größenordnung der Primteiler
ausgerichtet, die man sucht. Will man bis 10
20
gehen, wählt man
B ≈
12 000.
14.4 Zur Anzahl der Punkte einer Kurve
Die Kenntnis der Ordnung einer elliptischen Kurve ist für viele Anwendungen
von großer Bedeutung. Zum Beispiel muss sichergestellt sein, dass die Gruppen-
ordnung einen großen Primteiler besitzt, wenn man die Kurve für ein krypto-
grafisches Verfahren einsetzen will. Die Bestimmung der Gruppenordnung er-
folgt z. B. mit dem
Algorithmus von Schoof
, den wir in diesem Abschnitt in seinen
Grundzügen angeben. Weiterhin beschreiben wir die Struktur der Gruppe
+)
und formulieren Aussagen zur Existenz elliptischer Kurven mit vorgegebener
Ordnung und Gruppenstruktur.
In diesem letzten Abschnitt setzen wir voraus: Es seien
(
E
,
F
ein endlicher Körper
|
F
|
=
q
=
p
m
,
p
=
2, 3 und
E
:
y
2
mit
char
F
=
=
σ
(
x
)
eine elliptische Kurve mit
σ
(
x
)=
x
3
+
ax
+
b ∈
F
[
x
]
.
