Cryptography Reference
In-Depth Information
9.12 Alternative models for elliptic curves
We have introduced elliptic curves using Weierstrass equations, but there are many different
models and some of them have computational advantages. We present the Montgomery
model and the twisted Edwards model. A mathematically important model, which we
do not discuss directly, is the intersection of two quadratic surfaces; see Section 2.5 of
Washington [
560
] for details. It is not the purpose of this topic to give an implementation
guide, so we refrain from providing the optimised addition algorithms. Readers are advised
to consult Sections 13.2 and 13.3 of [
16
]orthe
Explicit Formulas Database
[
49
].
9.12.1 Montgomery model
This model, for elliptic curves over fields of odd characteristic, was introduced by
Montgomery [
392
] in the context of efficient elliptic curve factoring using (
x
:
z
) coor-
dinates. It is a very convenient model for arithmetic in (a projective representation of) the
algebraic group quotient
E
(
P
. Versions of the
Montgomery model have been given in characteristic 2, but they are not so successful; we
refer to Stam [
519
] for a survey.
k
) modulo the equivalence relation
P
≡−
Definition 9.12.1
Let
k
be a field such that char(
k
)
=
2. Let
A,B
∈ k
,
B
=
0. The
Mont-
gomery model
is
By
2
x
3
Ax
2
=
+
+
x.
(9.13)
1, the Montgomery model is not an elliptic
curve. However, the theory all goes through in the more general case, and so we refer to
curves in Montgomery model as elliptic curves.
According to Definition
7.2.8
, when
B
=
Exercise 9.12.2
Show that the Montgomery model is non-singular if and only if
B
(
A
2
−
4)
=
0.
Exercise 9.12.3
Show that there is a unique point at infinity on the Montgomery model of
an elliptic curve. Show that this point is not singular, and is always
k
-rational.
2
. Let E
:
y
2
x
3
a
2
x
2
Lemma 9.12.4
Let
k
be a field such that
char(
k
)
=
=
+
+
a
4
x
+
a
6
be an elliptic curve over
k
in Weierstrass form. There is an isomorphism over
k
from E to
x
3
a
2
x
2
a Montgomery model if and only if F
(
x
)
=
+
+
a
4
x
+
a
6
has a root x
P
∈ k
such
that
(3
x
P
+
2
a
2
x
P
+
a
4
)
is a square in
k
. This isomorphism maps
O
E
to the point at infinity
on the Montgomery model and is a group homomorphism.
Proof
Let
P
=
(
x
P
,
0)
∈
E
(
k
). First, move
P
to (0
,
0) by the change of variable
x
P
,y
) is an isomorphism to
y
2
X
3
a
2
X
2
a
4
X
X
=
x
−
x
P
.Themap(
x,y
)
→
(
x
−
=
+
+
=
a
4
, which lies in
where
a
2
=
a
2
and
a
4
=
3
x
P
+
3
x
P
+
2
a
2
x
P
+
a
4
.Let
w
k
by the
assumption of the Lemma. Consider the isomorphism (
X,y
)
→
(
U,V
)
=
(
X/w,y/w
) that
