Cryptography Reference
In-Depth Information
9.8 Multiplication by
n
and division polynomials
m
2
and so there are at most
m
2
points of order dividing
m
on an elliptic curve. There are several other explanations for
this fact. One explanation is to consider elliptic curves over
Corollary
9.6.28
showed the fundamental fact that deg([
m
])
=
C
: as a Riemann surface, they
are a complex torus
/L
where
L
is a rank 2 lattice (see Chapter 5 of Silverman [
505
],
especially Proposition 5.4) and it follows that there are
m
2
points of order
m
(this argument
generalises immediately to Abelian varieties).
It follows from Corollary
9.6.28
that #
E
[
m
]
C
m
2
, and elementary group theory implies
#
E
[
m
] is therefore a divisor of
m
2
. Theorem
9.8.1
follows. A more precise version of this
result is Theorem
9.10.13
.
≤
Theorem 9.8.1
Let E be an elliptic curve over a finite field
F
q
)
is isomorphic
as a group to a product of cyclic groups of order n
1
and n
2
such that n
1
|
F
q
. Then E
(
n
2
.
Proof
(Sketch) Since
E
(
F
q
) is a finite Abelian group we apply the classification of finite
Abelian groups (e.g., Theorem II.2.1 of [
271
]). Then use the fact that there are at most
m
2
points in
E
(
F
q
) of order
m
for every
m
∈ N
.
m
2
(and, by Corollary 9.7.3, equal to
m
2
when
m
is coprime to the
characteristic) it is natural to seek polynomials whose roots give the (affine) points of
order dividing
m
. We already saw such polynomials in Exercise
9.6.10
for the case
m
Since #
E
[
m
]
≤
=
2
k
(and this gave an alternative proof that, in general, there are three points (
x,y
) over
of
order 2 on an elliptic curve; namely, the points (
x,
0) where
x
is a root of the polynomial
in equation (
9.9
)). Since [
m
]
P
=
O
E
if and only if [
m
](
−
P
)
=
O
E
one might expect to
use polynomials in
[
x
], but when
m
is even it turns out to be more convenient to have
polynomials that feature the variable
y
(one reason being that this leads to polynomials of
lower degree). When
m
is odd the polynomials will be univariate and of degree (
m
2
k
−
1)
/
2
as expected. We now determine these polynomials, first for the cases
m
=
3 and
m
=
4.
Let
E
:
y
2
x
3
a
2
x
2
Exercise 9.8.2
=
+
+
a
4
x
+
a
6
be an elliptic curve over
k
(with
char(
k
)
=
2). Show that if char(
k
)
=
3,
a
2
=
0 and
a
4
=
0 then there is no point (
x,y
)
k
=
3 and
a
2
=
of order 3. Show that if char(
)
0 then (
x,y
) has order 3 if and only if
x
3
=
a
6
−
a
4
/
(4
a
2
). Hence, if char(
k
=
∈{
}
)
3 then #
E
[3]
1
,
3
.
Show that if char(
k
)
=
3 then (
x,y
) has order 3 if and only if
3
x
4
4
a
2
x
3
6
a
4
x
2
a
4
)
+
+
+
12
a
6
x
+
(4
a
2
a
6
−
=
0
.
Exercise 9.8.3
Let
E
:
y
2
x
3
=
+
a
4
x
+
a
6
be an elliptic curve over
k
with char(
k
)
=
2.
Show that if
P
=
(
x,y
)
∈
E
(
k
) satisfies
P
∈
E
[4] and
P
∈
E
[2] then [2]
P
is of the form
(
x
2
,
0) for some
x
2
∈ k
. Hence, show that
x
satisfies
x
6
5
a
4
x
4
20
a
6
x
3
5
a
4
x
2
(
a
4
+
8
a
6
)
.
+
+
−
−
4
a
4
a
6
x
−
We now state the polynomials whose roots give affine points of order dividing
m
for the
case of elliptic curves in short Weierstrass form. The corresponding polynomials for elliptic
