Cryptography Reference
In-Depth Information
Therefore, the subgroups
C
1
=
{∞
,P
1
,
−
P
1
}
and
C
2
=
{∞
,P
2
,
−
P
2
}
are such
that
φ
(
P
)=
λ
i
P
for all
P
∈
C
i
,where
λ
1
=1and
λ
2
=
−
1.
The polynomials
F
(
x
)are
x
−
1for
C
1
and
x
−
14 for
C
2
. They are factors
of the third division polynomial
3
x
3
+3
x
2
+9
x
+1
1)(3
x
+4)(
x
2
+15
x
+ 6)
ψ
3
(
x
)
≡
≡
(
x
−
(mod 23)
.
Either of
λ
1
,λ
2
can be used to obtain
a
mod 3:
a ≡ λ
i
+
23
λ
i
≡
0(mod
.
Therefore, #
E
(
F
23
)=23+1
− a ≡
0 (mod 3). Since
x
3
+
x
+7 has
x
=
−
3 as a root mod 23,
E
(
F
23
) contains a point of order 2. Therefore,
#
E
(
F
23
)
≡
0 (mod 6). The Hasse bounds tell us that 15
≤
#
E
(
F
23
)
≤
33,
hence #
E
(
F
23
) = 18, 24, or 30. In fact, counting points explicitly shows that
the group has order 18.
Let
E
i
be the image of the isogeny with kernel
C
i
.The
j
-invariant of
E
is
18. The modular polynomial Φ
3
(18
,T
) factors as
(
T
+1)(
T
+3)(
T
2
+2
T
+ 10)
Φ
3
(18
,T
)
≡
(mod 23)
(the polynomial Φ
3
is given on page 329). Therefore, there are two 3-isogenous
curves whose
j
-invariants are in
F
23
.Theyhave
j
=
−
1and
j
=
−
3. One of
these is
E
1
and the other is
E
2
. Which is which? (Exercise 12.14).
The following result, due to Atkin, shows that the possible factorizations of
Φ
(
j, T
)mod
are rather limited.
THEOREM 12.22
Let
E
be an elliptic curve defined over
F
p
. A ssu m e that
E
is n ot su persingular
and that its
j
-invariant
j
is not 0 or 1728. Let
=
p
be prime.Let
Φ
(
j, T
)
≡ f
1
(
T
)
···f
s
(
T
)(mod
)
be the factorization of
Φ
(
j, T
)
intoirredu ciblepolynom ialsmod
. T he degrees
of the factors are one of the follow ing:
1. 1 and
(an d
s
=2
)
2.
1
,
1
,r,r,...,r
(an d
s
=2+(
−
1)
/r
)
3.
r,r,...,r
(an d
s
=(
+1)
/r
).
In (1),
a
2
−
4
p ≡
0(mod
)
.In(2),
a
2
−
4
p
isasquaremod
.In(3),
a
2
−
4
p
is not a square m od
. In cases (2) an d (3),
a
2
≡
(
ζ
+2+
ζ
−
1
)
p
(mod
)
forsomeprimitive
r
throotofunity
ζ ∈
F
.
Search WWH ::
Custom Search