Cryptography Reference
In-Depth Information
Exercise 9.12.10
Show that every elliptic curve
E
in Montgomery model over a finite field
F
q
is such that either
E
or its quadratic twist
E
(
d
)
has a point of order 4.
Theorem 9.12.11
Let E be an elliptic curve over
F
q
(
char(
F
q
)
=
2
) such that
4
|
#
E
(
F
q
)
.
Then E is either isomorphic or 2-isogenous over
F
q
to an elliptic curve in Montgomery
model.
Proof
Suppose
P
∈
E
(
F
q
) has order 4. Write
P
0
=
[2]
P
and change coordinates so that
P
0
=
(0
,
0). By Exercise
9.12.8
it follows that
a
4
is a square in
F
q
and so by Lemma
9.12.4
is isomorphic to an elliptic curve in Montgomery model.
Suppose now that there is no point of order 4 in
E
(
F
q
). Then #
E
(
F
q
)[2]
=
4 and so all
F
q
. In other words, one can write
E
as
y
2
points of order 2 are defined over
=
x
(
x
−
a
)(
x
−
x
(
x
2
b
)
=
−
(
a
+
b
)
x
+
ab
) where
a,b
∈ F
q
. Now take the 2-isogeny as in Example
9.6.9
.
This maps
E
to
E
:
Y
2
b
)
2
). By Lemma
9.12.4
it follows
that
E
is isomorphic to an elliptic curve in Montgomery model.
X
(
X
2
=
+
2(
a
+
b
)
X
+
(
a
−
We have already seen the quadratic twist of a Montgomery model. It is natural to consider
whether there are other twists.
p
n
where p>
3
is prime. If E/
Theorem 9.12.12
Let q
F
q
is an ordinary elliptic curve
admitting a Montgomery model then only one non-trivial twist also admits a Montgomery
model. Furthermore, this twist is the quadratic twist.
=
Proof
When
j
(
E
)
0
,
1728 then the quadratic twist is the only non-trivial twist, so there
is nothing to prove. So we consider
j
(
E
)
=
=
=
1728 and
j
(
E
)
0. The crucial observation
will be that the other twists
E
do not satisfy 4
|
#
E
(
F
q
).
By Example
9.10.20
,if
j
(
E
)
=
1728 then
q
≡
1(mod4),
q
=
a
2
+
b
2
for some
a,b
∈
Z
, and the group orders are
q
+
1
±
2
a
and
q
+
1
±
2
b
. Note that, without loss of generality,
a
2
b
2
is such that
a
is odd and
b
is even. Then 2
a
the solution (
a,b
)to
q
=
+
≡
2
b
(mod 4)
and so only one of
q
+
1
+
2
a
and
q
+
1
+
2
b
is divisible by 4. Since
q
+
1
+
2
a
≡
q
2
a
(mod 4) (and similarly for the other case) it follows that only one pair of
quadratic twists can be given in Montgomery model.
By Exercise
9.10.22
,if
j
(
E
)
+
1
−
a
2
b
2
for some
a,b
=
0 then
q
≡
1(mod3),
q
=
+
ab
+
∈
Z
, and the possible group orders are
q
+
1
±
(
a
−
b
)
,q
+
1
±
(2
a
+
b
)
,q
+
1
±
(2
b
+
a
)
.
Without loss of generality,
a
is odd and
b
may be either odd or even. If
a
and
b
are both
odd then 2
a
−
b
and 2
b
−
a
are both odd and so
q
+
1
±
(
a
+
b
) is the only pair of group
orders that are even. Similarly, if
a
is odd and
b
is even then
a
+
b
and 2
b
+
a
are both odd
and so
q
+
1
±
(2
a
+
b
) is the only pair of group orders that are even. This completes the
proof.
E
xa
mple 9.12.13
The elliptic curve
y
2
x
3
=
+
a
4
x
is isomorphic
ov
er
k
to the curve
√
a
4
Y
2
(
x/
√
a
4
,y/a
4
).
X
3
=
+
X
in Montgomery form via (
x,y
)
→
(
X,Y
)
=
