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