Cryptography Reference
In-Depth Information
by expanding in terms of
x
we obtain
x
3
2
x
2
x
1
)
2
)
−
λ
+
(
a
−
2
λ
(
y
1
−
λ
x
1
))
x
+
(
b
−
(
y
1
−
λ
=
0
.
2
. Since
This polynomial equation of degree 3 clearly has three roots whose sum is
λ
x
1
and
x
2
are known roots, the third one is simply
2
x
3
=
λ
−
x
1
−
x
2
.
It corresponds to the third intersection point. Due to the equation of the line, we notice
that (
x
3
,
−
y
3
) is this third point (see Fig. 6.8). (
x
3
,
−
y
3
) is therefore on the curve, so
P
3
is as well.
We summarize important facts on elliptic curves.
Theorem 6.9.
Given a finite field
K
of characteristic p
>
3
and given a
,
b
∈
K
such
that
4
a
3
27
b
3
+
=
0
, we let E
a
,
b
be the elliptic curve as defined in Def. 6.8.
1. E
a
,
b
together with the point addition forms an Abelian group where
O
is the
neutral element.
2. For any a
and b
, the group E
a
,
b
is isomorphic to the group E
a
,
b
if and only
bu
6
.
3. Two isomorphic elliptic curves on
K
have the same j -invariant. The converse
is true when
K
is algebraically closed.
K
∗
such that a
=
au
4
and b
=
if there exists some u
∈
Proof (sketch).
To prove the first property, we notice that addition is trivially commu-
tative, with a neutral element
O
and that every
P
point has an opposite
−
P
point such
that
P
. We already saw that addition is internal in
E
a
,
b
. What remains
to prove is associativity. This part can be proven in a sophisticated way or through an
exhausting computation.
+
(
−
P
)
=
O
u
3
y
) defines a mapping
from
E
a
,
b
to
E
u
4
a
,
u
6
b
. We further notice that it is a group isomorphism. The converse
is true as well.
(
u
2
x
For the second property we notice that (
x
,
y
)
→
,
For the third property, we notice that if
E
a
,
b
and
E
a
,
b
are isomorphic, then we can
write
a
=
a
3
and the two curves have
the same
j
-invariant. We omit the proof for the converse result.
au
4
and
b
=
bu
6
. Therefore (
b
)
2
/
(
a
)
3
=
b
2
/
Let
a
=
and
b
=
K
∗
. Obviously, when
a
v
2
b
v
3
for some
v
∈
v
is a quadratic
residue, it can be written
v
=
u
2
and we define an isomorphic group
E
a
,
b
. One may
wonder what happens when
is a not a quadratic residue. Obviously, we obtain another
curve whose isomorphism class depends on the isomorphism class of
E
a
,
b
only. It is
actually called the
twist
of the curve. Note that although a curve and its twist share
the same
j
-invariant, they are usually not isomorphic. Their cardinality is actually
complementary in the sense of the following theorem.
v
Search WWH ::
Custom Search