Cryptography Reference
In-Depth Information
Then we obtain the elliptic curve
E
3
given by
Y
3
=
X
3
−
2
aX
3
+(
a
2
−
4
b
)
X
3
.
The map
α
:
E
E
3
is the same as the isogeny of Example 12.3.
The elliptic curve
E
3
has (0
,
0) as a point of order 2. Repeating the proce-
dure for
E
3
yields an isogeny to the elliptic curve
→
E
4
:
Y
4
=
X
4
+4
aX
4
+16
bX
4
with
X
4
=
X
3
+
−
2
aX
3
+
a
2
(
a
2
−
4
b
−
4
b
)
Y
3
X
3
,
4
=
Y
3
−
.
X
3
Let
X
5
=
X
4
/
4
,Y
5
=
Y
4
/
8. Then
Y
5
=
X
5
+
aX
5
+
bX
5
,
which is the equation of our original elliptic curve
E
. A calculation shows
that in the map
E
→
E
,
x → X
5
=
3
x
2
+2
ax
+
b
2
− a −
2
x,
2
y
which is exactly the formula for the
x
-coordinate of 2(
x, y
). A similar calcu-
lation for the
y
-coordinate tells us that the map
E → E
is multiplication by
2.
Insummary,wehaveanisogeny
α
:
E → E
3
and an isogeny
α
:
E
3
→ E
such that
α ◦ α
is multiplication by 2. The map
α
is an example of a dual
isogeny.
12.4 Point Counting
In Section 4.5, we discussed the method of Schoof for counting the number
of points on an elliptic curve over a finite field. In the present section, we
briefly sketch some work of Elkies and Atkin that uses isogenies to improve
the eciency of Schoof's algorithm.
Let
E
be an elliptic curve defined over
F
p
.The
p
-power Frobenius endo-
morphism satisfies
φ
2
−aφ
+
p
= 0 for some integer
a
,and#
E
(
F
p
)=
p
+1
−a
.
Therefore, to count the number of points in
E
(
F
p
), it suces to find
a
.
Let
=
p
be prime. Since the case
= 2 can be treated as in Section 4.5,
assume
is odd. The goal is to compute
a
(mod
). As in Schoof's algorithm,
Search WWH ::
Custom Search