Cryptography Reference
In-Depth Information
Let's compute (3
,
1) + (2
,
4) on
E
. The slope of the line through the two
points is
4
−
1
2
3
≡
2(mod
.
−
Thelineistherefore
y
=2(
x−
3)+1
≡
2
x
. Substituting this into
y
2
=
x
3
+
x
+1
and rearranging yields
0=
x
3
4
x
2
+
x
+1
.
−
The sum of the roots is 4, and we know the roots 3 and 2. Therefore the
remaining root is
x
=4. Since
y
=2
x
,wehave
y ≡
3. Reflecting across the
x
-axis yields the sum:
(3
,
1) + (2
,
4) = (4
,
2)
.
(Of course, we could have used the formulas of Section 2.2 directly.) A little
calculation shows that
E
(
F
5
) is cyclic, generated by (0
,
1) (Exercise 4.1).
Example 4.2
Let
E
be the elliptic curve
y
2
=
x
3
+2over
F
7
.Then
E
(
F
7
)=
{∞
,
(0
,
3)
,
(0
,
4)
,
(3
,
1)
,
(3
,
6)
,
(5
,
1)
,
(5
,
6)
,
(6
,
1)
,
(6
,
6)
}
.
An easy calculation shows that all of these points
P
satisfy 3
P
=
∞
,sothe
group is isomorphic to
Z
3
⊕
Z
3
.
Example 4.3
Let's consider the elliptic curve
E
given by
y
2
+
xy
=
x
3
+ 1 defined over
F
2
.
Wecanfindthepointsasbeforeandobtain
E
(
F
2
)=
{∞,
(0
,
1)
,
(1
,
0)
,
(1
,
1)
}.
This is a cyclic group of order 4. The points (1
,
0)
,
(1
,
1) have order 4 and the
point (0
,
1) has order 2.
Now let's look at
E
(
F
4
). Recall that
F
4
is the finite field with 4 elements.
We can write it as
F
4
=
{
0
,
1
,ω,ω
2
}
, with the relation
ω
2
+
ω
+1=0 (which
implies, after multiplying by
ω
+1, that
ω
3
= 1). Let's list the elements of
E
(
F
4
).
x
=0
⇒ y
2
=1
⇒ y
=1
x
=1
⇒ y
2
+
y
=0
⇒ y
=0
,
1
x
=
ω ⇒ y
2
+
ωy
=0
⇒ y
=0
,ω
x
=
ω
2
⇒ y
2
+
ω
2
y
=0
⇒ y
=0
,ω
2
x
=
∞⇒
y
=
∞
.
Therefore
E
(
F
4
)=
∞,
(0
,
1)
,
(1
,
0)
,
(1
,
1)
,
(
ω,
0)
,
(
ω, ω
)
,
(
ω
2
,
0)
,
(
ω
2
,ω
2
)
.
Search WWH ::
Custom Search