Cryptography Reference
In-Depth Information
14.4.1 Der Satz von Hasse
Wir zeigen, dass für die Menge der Quadrate in
F
gilt:
x
2
;
x
∈
F
\{
=
q
−
1
0
}
.
2
x → x
2
F
\{
}→
F
\{
}
Die Abbildung
Ψ
:
0
0
,
ist ein Homomorphismus mit
und dem Bild
x
2
;
x
}
. Aus dem Homomorphiesatz
{±
}
∈
F
\{
dem Kern
1
0
von Seite 150 folgt somit die Behauptung.
Zu gegebenem
u
∈
F
σ
(
u
)
etwa in der Hälfte aller Fälle ein Quadrat und
liefert in diesen Fällen zwei Punkte der elliptischen Kurve. Man erwartet daher
etwa
q
Punkte auf
E
. In der Tat hat man den Satz (siehe [26]):
ist also
Satz 14.1
(Hasse)
Es sei E eine elliptische Kurve über
F
mit
|
F
|
=
q. Dann gilt
2
√
q
.
|
E
|
=
q
+
1
−
t mit
|
t
|≤
Man beachte, dass
t
die
Abweichung
der Punktanzahl von
E
von der Anzahl der
Punkte auf einer projektiven Geraden angibt.
Der Algorithmus von Schoof, der in Abschnitt 14.4.5 dargestellt wird, ist eine
Methode mit der
t
und damit
|E|
effizient bestimmt werden kann.
Beispiel
p
:
2
160
1461501637330902918203684832716283019655932542983 ist eine
Primzahl. Die Anzahl der Punkte
N
jeder elliptischen Kurve über
=
+
7
=
Z
p
liegt im
Intervall
146150163733090291820368 2414864643790397583130631
≤ N ≤
146150163733090291820368 7250567922248914281955335
Die Stelle an der die Zahlen zum ersten Mal voneinander abweichen ist markiert.
Man erkennt, dass die Ober- und die Untergrenze sich nur relativ wenig unter-
scheiden.
Bemerkung
Um eine Kurve mit ungefähr 2
160
10
48
Punkten zu erhalten, braucht man
≈
1.4
·
2
160
. Die Abweichung ist höchsten in der Größenordnung von 10
25
.
also
q ≈
Das oben beschriebene heuristische Argument liefert eine effiziente Methode, um
Punkte auf elliptischen Kurven zu gewinnen.
Wähle zufällig ein Element
u
∈
F
.
Prüfe, ob
σ
(
u
)
ein Quadrat in
F
ist.
