Cryptography Reference
In-Depth Information
Figure 1.2
y
2
=
x
(
x
+ 1)(2
x
+1)
/
6
in positive integers
x, y
. An equation of this type represents an
elliptic curve
.
The graph is given in Figure 1.2.
The method of Diophantus uses the points we already know to produce new
points. Let's start with the points (0,0) and (1,1). The line through these two
points is
y
=
x
. Intersecting with the curve gives the equation
x
2
=
x
(
x
+ 1)(2
x
+1)
6
=
1
3
x
3
+
1
2
x
2
+
1
6
x.
Rearranging yields
3
2
x
2
+
1
x
3
2
x
=0
.
Fortunately, we already know two roots of this equation:
x
=0and
x
=1.
This is because the roots are the
x
-coordinates of the intersections between
the line and the curve. We could factor the polynomial to find the third root,
but there is a better way. Note that for any numbers
a, b, c
,wehave
−
(
x − a
)(
x − b
)(
x − c
)=
x
3
−
(
a
+
b
+
c
)
x
2
+(
ab
+
ac
+
bc
)
x − abc.
Therefore, when the coecient of
x
3
is 1, the negative of the coecient of
x
2
is the sum of the roots.
In our case, we have roots 0
,
1, and
x
,so
0+1+
x
=
3
2
.
Therefore,
x
=1
/
2. Since the line was
y
=
x
,wehave
y
=1
/
2, too. It's hard
to say what this means in terms of piles of cannonballs, but at least we have
found another point on the curve. In fact, we automatically have even one
more point, namely (1
/
2
, −
1
/
2), because of the symmetry of the curve.
Search WWH ::
Custom Search