Cryptography Reference
In-Depth Information
invariant
j
2
. It is easy to see from the construction of Φ
(
x
) that its degree is
+ 1, corresponding to the
+ 1 subgroups in
E
[
]oforder
+1. Since Φ
has
integer coe
cients, we can regard it as a polynomial mod
p
. The following
analogue of Theorem 12.5 holds.
THEOREM 12.19
Let
=
p
be prime, et
j
1
,j
2
∈
F
p
,and et
E
1
,E
2
be elliptic curves w ith
invariants
j
1
,j
2
.Then
Φ
(
j
1
,j
2
)=0
ifand onlyifthere isanisogeny fro m
E
1
to
E
2
of degree
.
PROPOSITION 12.20
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.
1. Let
j
1
∈
F
p
be a root of the polynom ial
Φ
(
j, T
)
,let
E
1
be an elliptic
curve ofinvariant
j
1
,and let
C
be the kernelofthe corresponding isogeny
E → E
1
ofdegree
.Let
r ≥
1
.Thereexists
ν ∈
Z
su ch that
φ
r
P
=
νP
for all
P ∈ C
ifand onlyif
j
1
∈
F
p
r
.
2. T he polynom ial
Φ
(
j, T
)
factors into inear factors over
F
p
r
ifand only
ifthere exists
ν ∈
Z
su ch that
φ
r
P
=
νP
for all
P ∈ E
[
]
.
If
φ
r
P
=
νP
for all
P
C
, then, as discussed previously, the
j
-invariant
j
1
oftheisogenouscurveisin
F
p
r
. Similarly, if
φ
r
P
=
νP
for all
P
PROOF
∈
E
[
], then all
-isogenous curves have
j
-invariants in
F
p
r
, so all roots of
Φ
(
j, T
)arein
F
p
r
.
For proofs of the converse statements, see [99].
∈
REMARK 12.21
The restriction to
j
=0
,
1728 is necessary. See Exercise
12.11.
By computing gcd (
T
p
− T,
Φ
(
j, T
)) as a polynomial in
F
,weobtaina
polynomial whose roots are the roots of Φ
(
j, T
)in
F
. Finding a root
j
1
of this polynomial allows us to construct a curve with
j
-invariant
j
1
(using
the formula on page 47) that is
-isogenous to
E
. As mentioned previously,
a rather complicated procedure, described in [12] and [99], yields the desired
factor
F
(
x
) of the division polynomial
ψ
(
x
).
Example 12.5
Consider the elliptic curve
E
:
y
2
=
x
3
+
x
+7 over
F
23
. The group
E
[3] is
generated by
P
1
=(1
,
3) and
P
2
=(14
,
√
5), where
√
5
∈
F
23
2
.Let
φ
be the
23rd power Frobenius endomorphism. Then
φ
(
P
1
)=
P
1
and
φ
(
P
2
)=
−P
2
.
Search WWH ::
Custom Search