Cryptography Reference
In-Depth Information
z
=
−
x
2
z
1
)
y
1
y
2
−A
(
x
1
z
2
+
x
2
z
1
)(
x
1
z
2
− x
2
z
1
)
−
3
B
(
x
1
z
2
− x
2
z
1
)
z
1
z
2
(
x
1
y
2
+
x
2
y
1
)(
y
1
z
2
−
y
2
z
1
)
−
(
x
1
z
2
−
3
Then the m atrix
⎛
⎞
x
3
y
3
z
3
x
3
y
3
z
3
x
3
y
3
z
⎝
⎠
3
isprimitive and all
2
2
su bdeterm inantsvanish. Take a primitive
R
-linear
com bination
(
x
3
,y
3
,z
3
)
of the rows. D efine
×
(
x
1
:
y
1
:
z
1
)+(
x
2
:
y
2
:
z
2
)=(
x
3
:
y
3
:
z
3
)
.
Also,define
y
1
:
z
1
)
.
Then
E
(
R
)
isanabe ian group under this definition of point addition. T he
identitye em ent is
(0:1:0)
.
−
(
x
1
:
y
1
:
z
1
)=(
x
1
:
−
For some of the details concerning this definition, see [74]. The equations
are deduced (with a slight correction) from those in [18]. A similar set of
equations is given in [72].
When
R
is a field, each of these equations can be shown to give the usual
group law when the output is a point in
P
2
(
R
) (that is, not all three coor-
dinates vanish). If two or three of the equations yield points in
P
2
(
R
), then
these points are equal (since the 2
×
2 subdeterminants vanish). If
R
is a ring,
then it is possible that each of the equations yields a nonprimitive output
(for example, perhaps 5 divides the output of I, 7 divides the output of II,
and 11 divides the output of III). If we are working with
Z
or
Z
(2)
,thisis
no problem. Simply divide by the gcd of the entries in an output. But in an
arbitrary ring, gcd's might not exist, so we must take a linear combination to
obtain a primitive vector, and hence an element in
P
2
(
R
).
Example 2.10
Let
R
=
Z
25
and let
E
be given by
y
2
=
x
3
− x
+1 (mod 5
2
)
.
Suppose we want to compute (1
,
1) + (21
,
4), as in Example 2.7 above. Write
the points in homogeneous coordinates as
(
x
1
:
y
1
:
z
1
)=(1:1:1)
,
(
x
2
:
y
2
:
z
2
)=(21:4:1)
.
Formulas I, II, III yield
(
x
3
,y
3
,z
3
)=(5
,
23
,
0)
(
x
3
,y
3
,z
3
)=(5
,
8
,
0)
(
x
3
,y
3
,z
3
)=(20
,
12
,
0)
,
Search WWH ::
Custom Search