Cryptography Reference
In-Depth Information
φ
(2
P
)=(1
,
1
,
1) for any point
P
, we always obtain an
x
such that
x
,
x
−
5,
and
x
+5 are squares when we double a point on the curve
y
2
=
x
(
x
−
5)(
x
+5).
Example 8.9
One use of descent is to find points on elliptic curves. The idea is that in the
equations
x − e
1
=
au
2
x
e
2
=
bv
2
−
e
3
=
cw
2
,
x
−
the numerators and denominators of
u, v, w
are generally smaller than those
of
x
. Therefore, an exhaustive search for
u, v, w
is faster than searching for
x
directly. For example, suppose we are looking for points on
y
2
=
x
3
−
36
x.
One of the triples that we encounter is (
a, b, c
)=(3
,
6
,
2).
This gives the
equations
x
=3
u
2
6=6
v
2
x
+6=2
w
2
.
x
−
These can be written as
3
u
2
−
6
v
2
=6
,
2
w
2
−
3
u
2
=6
,
which simplify to
3
u
2
=6
.
A quick search through small values of
u
yields (
u, v, w
)=(2
,
1
,
3). This gives
u
2
2
v
2
=2
,
2
w
2
−
−
(
x, y
)=(12
,
36)
.
Note that the value of
u
is smaller than
x
. Of course, we are lucky in this
example since the value of
u
turned out to be integral. Otherwise, we would
have had to search through values of
u
with small numerator and small de-
nominator.
The curve
y
2
=
x
3
−
36
x
can be transformed to the curve
y
2
=
x
(
x
+1)(2
x
+
1)
/
6 that we met in Chapter 1 (see Exercise 1.5). The point (1
/
2
,
1
/
2) on
that curve corresponds to the point (12
,
36) that we found here.
Example 8.10
The elliptic curves that we have seen up to now have had small generators
for their Mordell-Weil groups. However, frequently the generators of Mordell-
Weil groups have very large heights. For example, the Mordell-Weil group of
Search WWH ::
Custom Search