Cryptography Reference
In-Depth Information
so the order of the kernel is the degree of
φ
q
−
1. A third major ingredient
is the Weil pairing, especially part (6) of Theorem 3.9, and its consequence,
Proposition 3.16.
Proposition 4.7 has another very useful consequence.
THEOREM 4.10
Let
E
be an elliptic curve defined over
F
q
.Let
a
be as inEquation 4.1. T hen
φ
q
− aφ
q
+
q
=0
as endom orphism s of
E
,and
a
isthe unique integer
k
su ch that
φ
q
−
kφ
q
+
q
=0
.
In o ther w ords, if
(
x, y
)
E
(
F
q
)
,then
x
q
2
,y
q
2
∈
a
(
x
q
,y
q
)+
q
(
x, y
)=
−
∞
,
and
a
isthe unique integer such thatthisrelation holds for all
(
x, y
)
∈
E
(
F
q
)
.
M oreover,
a
isthe unique integer satisfying
a
≡
Trace((
φ
q
)
m
)mod
m
for all
m
with
gcd(
m, q
)=1
.
If
φ
q
−
aφ
q
+
q
is not the zero endomorphism, then its kernel
is finite (Proposition 2.21). We'll show that the kernel is infinite, hence the
endomorphism is 0.
Let
m
PROOF
1 be an integer with gcd(
m, q
) = 1. Recall that
φ
q
induces a
matrix (
φ
q
)
m
that describes the action of
φ
q
on
E
[
m
]. Let
(
φ
q
)
m
=
st
≥
.
uv
Since
φ
q
−
1 is separable by Proposition 2.29, Propositions 2.21 and 3.15 imply
that
#Ker(
φ
q
−
1) = deg(
φ
q
−
1)
≡
det((
φ
q
)
m
−
I
)
=
sv
−
tu
−
(
s
+
v
)+1 (mod
m
)
.
By Proposition 3.15,
sv
−
tu
= det((
φ
q
)
m
)
≡
q
(mod
m
). By (4.1), #Ker(
φ
q
−
1) =
q
+1
−
a
. Therefore,
Trace((
φ
q
)
m
)=
s
+
v ≡ a
(mod
m
)
.
Search WWH ::
Custom Search