Cryptography Reference
In-Depth Information
law allows us to make these computations without worrying about what order
we use to combine the summands.
The method of successive doubling can be stated in general as follows:
INTEGER TIMES A POINT
Let
k
be a positive integer and let
P
be a point on an elliptic curve. T he
follow ing procedure com putes
kP
.
1. Start w ith
a
=
k, B
=
∞,C
=
P
.
2. If
a
is even, let
a
=
a/
2
,and let
B
=
B, C
=2
C
.
3. If
a
is odd, let
a
=
a −
1
,and let
B
=
B
+
C, C
=
C
.
4. If
a
=0
,go tostep 2.
5. O utput
B
.
Theoutput
B
is
kP
(see E xercise 2.8).
On the other hand, if we are working over a large finite field and are given
points
P
and
kP
, it is very di
cult to determine the value of
k
. This is called
the
discrete logarithm problem
for elliptic curves and is the basis for the
cryptographic applications that will be discussed in Chapter 6.
2.3 Projective Space and the Point at Infinity
We all know that parallel lines meet at infinity. Projective space allows us
to make sense out of this statement and also to interpret the point at infinity
on an elliptic curve.
Let
K
be a field. Two-dimensional
projective space P
2
K
over
K
is given by
equivalence classes of triples (
x, y, z
) with
x, y, z ∈ K
and at least one of
x, y, z
nonzero. Two triples (
x
1
,y
1
,z
1
)and(
x
2
,y
2
,z
2
)aresaidtobe
equivalent
if
there exists a nonzero element
λ ∈ K
such that
(
x
1
,y
1
,z
1
)=(
λx
2
,λy
2
,λz
2
)
.
We write (
x
1
,y
1
,z
1
)
∼
(
x
2
,y
2
,z
2
). The equivalence class of a triple only
depends on the ratios of
x
to
y
to
z
.
Therefore, the equivalence class of
(
x, y, z
) is denoted (
x
:
y
:
z
).
If (
x
:
y
:
z
) is a point with
z
=0,then(
x
:
y
:
z
)=(
x/z
:
y/z
: 1). These
are the “finite” points in
P
2
K
. However, if
z
= 0 then dividing by
z
should
be thought of as giving
∞
in either the
x
or
y
coordinate, and therefore the
points (
x
:
y
: 0) are called the
“points at infinity”
in
P
2
K
.Thepointat
Search WWH ::
Custom Search