Cryptography Reference
In-Depth Information
Figure 2.3
An Elliptic Curve over C
4. If E is defined over R ,then E ( R ) is isomorphic to the unit circle S 1
or to S 1
Z 2 . The first case corresponds to the case where the cubic
polynomial x 3 + Ax + B has only one real root (think of the ends of the
graph in Figure 2.1(b) as being hitched together at the point to get a
loop). The second case corresponds to the case where the cubic has three
real roots. The closed loop in Figure 2.1(a) is the set S 1
⊕{ 1 } , while the
open-ended loop can be closed up using to obtain the set S 1
⊕{ 0 } .
If we have an elliptic curve E defined over R , then we can consider its
complex points E ( C ). These form a torus, as in (3) above. The real
points E ( R ) are obtained by intersecting the torus with a plane. If the
plane passes through the hole in the middle, we obtain a curve as in
Figure 2.1(a). If it does not pass through the hole, we obtain a curve as
in Figure 2.1(b) (see Section 9.3).
If P is a point on an elliptic curve and k is a positive integer, then kP
denotes P + P + ··· + P (with k summands). If k< 0, then kP =( −P )+
( −P )+ ··· ( −P ), with |k| summands. To compute kP for a large integer k ,it
is inecient to add P to itself repeatedly. It is much faster to use successive
doubling . For example, to compute 19 P , we compute
2 P,
4 P =2 P +2 P,
8 P =4 P +4 P,
16 P =8 P +8 P,
19 P =16 P +2 P + P.
This method allows us to compute kP for very large k , say of several hundred
digits, very quickly. The only diculty is that the size of the coordinates of
the points increases very rapidly if we are working over the rational numbers
(see Theorem 8.18). However, when we are working over a finite field, for
example F p , this is not a problem because we can continually reduce mod p
and thus keep the numbers involved relatively small. Note that the associative
 
Search WWH ::




Custom Search