Cryptography Reference
In-Depth Information
2
(c) In
End
E
(
F
)
gilt φ
−
[
t
]
φ
+[
q
]=[
0
]
.
Beweis.
(a) und (c) siehe [26].
(b) Die Ho
m
omorphie ist klar. Es gilt
[
k
]=[
0
]
genau dann, wenn
kP
=
O
fü
r
alle
P ∈ E
(
F
)
. Aber nach (a) gibt es Punkte mit beliebig großer Ordnung in
E
(
F
)
,
sodass
k
=
0 gelten muss. Daher ist der Kern des Homomorphismus trivial.
Auf Grund dieses Satzes heißt
t
auch die
Spur des Frobenius
.
14.4.5 Der Algorithmus von Schoof
Ziel ist es, die Ordnung der Gruppe
E
zu finden. Wegen des Satzes 14.5 ist das
gleichbedeutend mit der Bestimmung der Spur des Frobenius
t
.
Die Zahl
t
ist modulo 2 bekannt. Mit unseren Voraussetzungen gilt nämlich:
Lemma 14.6
0
(
mod 2
)
,
falls σ eine Nullstelle in
F
besitzt,
t
≡
,
falls nicht.
Beweis.
Die Anzahl aller Punkte mit
P
=
−P
ist gerade; sie müssen modulo 2
also nicht berücksichtigt werden. Für die verbleibenden Punkte gilt 2
P
(
)
1
mod 2
=
O
.
Ein Punkt
P
der Ordnung 2 hat die Form
P
=(
u
,0
, denn nur indiesem Fall gilt
O∈T
P
, vgl. Lemma 13.6. Es ist dann
u
eine Nullstelle von
)
σ
. Umgekehrt liefert
jede Nullstelle von
einen Punkt der Ordnung 2. Daher gibt es einen oder drei
Punkte der Ordnung 2, wenn
σ
σ
Nullstellen in
F
besitzt, sonst gibt es keine.
Dazu kommt der Punkt
O
, der auch die Eigenschaft 2
O
=
O
besitzt.
|E|
=
q
+
− t ≡ t
(
)
Schließlich gilt
1
mod 2
. Daraus folgt die Behauptung.
=
p
ist nach Satz 14.5 (a)
E
[
] =
Z
×
Z
Für eine ungerade Primzahl
ein
Z
-
Vektorraum. Ist
P ∈ E
[
]
P
=
O
φ
(
P
)=
O
, so gilt
, also auch
. Daher ist
φ
:
E
[
]
→
E
[
]
,
P
→
φ
(
P
)
ein wohldefinierter Homomorphismus, der, wie man leicht sieht, sogar
Z
-
linear ist. Die Gleichung aus Satz 14.5
(c
) gilt dann für
φ
. Für die Zahl
t
∈
{−
−
1
2
,...,
−
1
2
}
mit
t ≡ t
(
)
.
Bevor wir auf die Schwierigkeit des Algorithmus von Schoof eingehen, geben wir
das Grundgerüst des Verfahrens an.
mod
ist
t
die Spur der linearen Abbildung
φ
4
√
q
.
max
∈
P
∏
∈
P
,
≤
max
≥
Wähle
minimal mit
Bestimme
t
2
∈{
0, 1
}
gemäß Lemma 14.6.
♦
Für alle
∈
P
mit
≤
max
wähle
P
∈
E
[
]
und teste für alle
τ
∈
{−
−
1
2
,...,
−
1
2
2
}
,ob
φ
(
P
)+
qP
=
τφ
(
P
)
. Im Erfolgsfall setze
t
:
=
τ
.
Bestimme die eindeutige Lösung des Systems von Kongruenzgleichungen
2
√
q ≤ t ≤
2
√
q
t ≡ t
(
)
≤
max
, die
−
mod
,
erfüllt.
Vgl. dazu den chinesischen Restsatz 7.4 und Abschnitt 7.2.2.
