Cryptography Reference
In-Depth Information
q
n
Exercise 9.10.9
Let
E
be an elliptic curve over
F
q
. Write #
E
(
F
q
n
)
=
−
t
n
+
1for
q
i
t
j
−
i
. Some special cases
n
∈ N
. Show that for
i,j
∈ N
with
i<j
we have
t
i
t
j
=
t
i
+
j
+
are
t
n
−
2
q
n
,t
n
+
1
=
t
2
n
=
t
n
t
1
−
qt
n
−
1
.
Hence, give an algorithm to efficiently compute
t
n
for any value
n
,given
q
and
t
1
.
Exercise 9.10.10
Let
E
a
:
y
2
x
3
ax
2
+
xy
=
+
+
1 over
F
2
where
a
∈{
0
,
1
}
. Show that
1)
a
T
2
1)
a
T
#
E
a
(
2. These curves are called
Koblitz
curves
(Koblitz called them
anomalous binary curves
). Show that if
n
is composite then
#
E
a
(
F
2
)
=
2
+
(
−
+
1so
P
(
T
)
=
+
(
−
+
F
2
n
) is not of the form 2
r
or 4
r
where
r
is prime. Hence, find all 3
<n<
200 such
that #
E
0
(
F
2
n
)
=
2
r
or #
E
1
(
F
2
n
)
=
4
r
where
r
is prime.
We have seen that the number of points on an elliptic curve over a finite field lies in
the Hasse interval. An important result of Waterhouse [
561
] specifies exactly which group
orders arise.
2
√
q. Then
p
m
and let t
Theorem 9.10.11
(Waterhouse) Let q
=
∈ Z
be such that
|
t
|≤
there is an elliptic curve over
F
q
with
#
E
(
F
q
)
=
q
−
t
+
1
if and only if one of the following
conditions holds:
1.
gcd(
t,p
)
1
;
2. m is even and t
=
2
√
q;
=±
=±
√
q;
3. m is even, p
≡
1(mod3)
and t
p
(
m
+
1)
/
2
;
5. Either m is odd or (m is even and p
4. m is odd, p
=
2
,
3
and t
=±
≡
1(mod4)
) and t
=
0
.
Proof
The proof given by Waterhouse relies on Honda-Tate theory; one shows that the
above cases give precisely the polynomials
T
2
−
tT
+
q
with roots being Weil numbers.
See Theorem 4.1 of [
561
].
t
), the elliptic curve is said to be
supersingular
.This
case is discussed further in Section
9.11
.
In the cases gcd(
t,p
)
=
1 (i.e.,
p
|
Example 9.10.12
Let
p
≡
3
(
mod4)beprime,let
g
∈ F
p
2
be a primitive root and
E
:
1
/
√
g
y
2
x
3
g
2
x
.Let
u
(
u
2
x,u
3
y
) that maps
=
+
=
∈ F
p
4
. Consider the map
φ
(
x,y
)
=
E
to
E
:
Y
2
X
.ByExercise
9.10.5
,#
E
(
X
3
(
u
4
g
2
)
X
X
3
=
+
=
+
F
p
)
=
p
+
1 and the
π
p
on
E
satisfies (
π
p
)
2
p
-power Frobenius map
=−
p
.
φ
−
1
(
w
1
x
p
,w
2
y
p
) where
w
1
=
Define
ψ
∈
End
F
q
(
E
)by
ψ
=
◦
π
p
◦
φ
. Then
ψ
(
x,y
)
=
u
3
p
/u
3
. One can verify that
w
1
,w
2
∈ F
p
2
(just show that
w
p
2
u
2
p
/u
2
and
w
2
=
=
w
i
)
i
and that
w
p
+
1
1
1 and
w
p
+
1
2
=
=−
1. Finally, one has
ψ
(
ψ
(
x,y
))
=
ψ
(
w
1
x
p
,w
2
y
p
)
=
(
w
p
+
1
1
x
p
2
,w
p
+
1
2
y
p
2
)
(
x
p
2
,
y
p
2
)
=
−
=−
π
p
2
(
x,y
)on
E
. On the other hand, by definition
ψ
2
φ
−
1
π
p
)
2
φ
−
1
=
◦
(
◦
φ
=
◦
[
−
p
]
◦
φ
=
[
−
p
]
