Divisors - Elliptic Curves: Number Theory and Cryptography - page 362

7. i =0 ,j =13 ,k =8 , ( v 13 ,v 8 )

Example 11.7
Let E be the elliptic curve

y 2 = x 3 − x +1

over F 11 ,andlet n = 5. There are 10 points in E ( F 11 ). The point P =(3 , 6)
has order 5. Let's compute P, P 5 . Therefore, in the definition of the Tate-
Lichtenbaum pairing, we have P = Q =(3 , 6). Let

D P =[(3 , 6)] − [ ∞ ] , D Q =[(1 , 1)] − [(0 , 1)] = [ Q 1 ] − [ Q 2 ] .

The divisor D Q was constructed by adding (0 , 1) to Q to obtain (1 , 1). This
wasdonesothat D P and D Q have no points in common. We now use the
algorithm to compute f P ( D Q ), where

div( f P )=5 D P .

In Equation (11.7), we have R = ∞ ,so D 0 = D 1 = 0. Therefore, we take
f 0 = f 1 = 1. The algorithm proceeds as follows.

1. Start with i =5 ,j =0 ,k =1 ,v 0 =1 ,v 1 =1.

2. Since i = 5 is odd, compute v j + k = v 1 , which is already known to be 1.
Update the values of i, j, k to obtain i =4 ,j =1 ,k =1 ,v 1 =1 ,v 1 =1.

3. Since i = 4 is even, compute the line tangent to E at kP = P .This
is 4 x y + 5 = 0. The vertical line through 2 kP =2 P is x +1 = 0.

Therefore, Equation (11.9) becomes

−

D Q

4 x y +5

x +1

−

v 2 = v 1 · =1 · 1=1 .

Here we performed the calculation

(4 x | (1 , 1)

(4 x − y +5) | (0 , 1)

− y +5)

= 8 (4 x − y +5) | D Q =

4 =2

and similarly ( x +1) | D Q = 2. Update to obtain i =2 ,j =1 ,k =2 ,v 1 =

1 ,v 2 =1.

4. Since i = 2 is even, use the computation of 4 P =2 P +2 P to obtain

D Q

x + y +2
x − 3

v 4 = v 2 · v 2 · =1 · 1 · 2=2 .

Update to obtain i =1 ,j =1 ,k =4 ,v 1 =1 ,v 4 =2.