Cryptography Reference
In-Depth Information
expressible in the form
m
1
β
1
+
m
2
β
with i
nte
gers
m
1
,
m
2
. Note that
m
1
,m
2
are uniquely determined mod
n
.Let
α
:
E
(
K
)
E
(
K
) be a homomorphism.
Then
α
maps
E
[
n
]into
E
[
n
]. Therefore, there are
a, b, c, d
→
∈
Z
n
such that
α
(
β
1
)=
aβ
1
+
cβ
2
,
α
(
β
2
)=
bβ
1
+
dβ
2
.
Therefore each homomorphism
α
:
E
(
K
)
→
E
(
K
) is represented by a 2
×
2
matrix
α
n
=
ab
.
cd
Composition of homomorphisms corresponds to multiplication of the corre-
sponding matrices.
In many cases, the homomorphism
α
will be taken to be an endomorphism,
which means that it is given by ration
al f
unctions (see Section 2.9). But
α
can also come from an automorphism of
K
that fixes
K
. This leads to the im-
portant subject of representations of Galois groups (that is, homomorphisms
from Galois groups to groups of matrices).
Example 3.1
Let
E
be the elliptic curve defined over
R
by
y
2
=
x
3
−
2, and let
n
=2.
Then
E
[2] =
{∞,
(2
1
/
3
,
0)
,
(
ζ
2
1
/
3
,
0)
,
(
ζ
2
2
1
/
3
,
0)
},
where
ζ
is a nontrivial cube root of unity. Let
β
1
=(2
1
/
3
,
0)
,
2
=(
ζ
2
1
/
3
,
0)
.
is a basis for
E
[2], and
β
3
=(
ζ
2
2
1
/
3
,
0) =
β
1
+
β
2
.
Let
α
:
E
(
C
)
Then
{
β
1
,β
2
}
E
(
C
) be complex conjugation:
α
(
x, y
)=(
x, y
), where
the bar denotes complex conjugation. It is easy to verify that
α
is a homo-
morphism. In fact, since all the c
oe
ci
en
ts
of the fo
rmulas for the group
law have real coecients, we have
P
1
+
P
2
=
P
1
+
P
2
. This is the same as
α
(
P
1
)+
α
(
P
2
)=
α
(
P
1
+
P
2
). We have
→
α
(
β
1
)=1
·
β
1
+0
·
β
2
,
α
(
β
2
)=
β
3
=1
·
β
1
+1
·
β
2
.
Therefore we obtain the matrix
α
2
=
11
. Note that
α
◦
α
is the identity,
01
which corresponds to the fact that
α
2
is the identity matrix mod 2.
3.2 Division Polynomials
The goal of this section is to prove Theorem 3.2. We'll also obtain a few
other results that will be needed in proofs in Section 4.2.
Search WWH ::
Custom Search