Cryptography Reference
In-Depth Information
du
1
v
1
u
2
v
2
=
−
1. Then
u
i
,v
i
=0and
u
1
v
1
=
−
1
/du
2
v
2
. Substituting into
the formula for
C
yields
u
1
+
v
1
=
c
2
1+
=
u
2
+
v
2
du
2
v
2
1
du
2
v
2
.
Therefore,
(
u
1
+
v
1
)
2
=
u
1
+
v
1
+2
u
1
v
1
u
2
+
v
2
−
=
v
2
)
2
(
u
2
v
2
)
2
1
d
2
u
2
v
2
1
d
(
u
2
−
.
=
u
2
v
2
Since
d
is not a square, this must reduce to 0 = 0, so
u
1
+
v
1
=0.
Similarly,
(
u
2
+
v
2
)
2
(
u
2
v
2
)
2
1
d
(
u
1
− v
1
)
2
=
,
which implies that
u
1
−
v
1
= 0. Therefore,
u
1
=
v
1
= 0, which is a contradic-
tion.
Thecasewhere
du
1
v
1
u
2
v
2
= 1 similarly produces a contradiction. There-
fore, the addition formula is always defined for points in
C
(
K
).
An interesting feature is that there are not separate formulas for 2
P
and
P
1
+
P
2
when
P
1
=
P
2
.
The formula for adding points can be written in projective coordinates. The
resulting computation takes 10 multiplications and 1 squaring for both point
addition and point doubling.
Although any elliptic curve can be put into the form of the proposition over
an algebraically closed field, this often cannot be done over the base field. An
easy way to see this is that there is a point of order 2. In fact, the point (
c,
0)
on
C
has order 4 (Exercise 2.7), so a curve that can be put into Edwards form
over a field must have a point of order 4 defined over that field.
2.7 The j-invariant
Let
E
be the elliptic curve given by
y
2
=
x
3
+
Ax
+
B
,where
A, B
are
elements of a field
K
of characteristic not 2 or 3. If we let
x
1
=
μ
2
x,
y
1
=
μ
3
y,
(2.8)
K
×
, then we obtain
with
μ
∈
y
1
=
x
1
+
A
1
x
1
+
B
1
,
Search WWH ::
Custom Search