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

For example, this means that if we know f j ( Q 1 ) /f j ( Q 2 )for j =2 i ,we
can quickly calculate the same expression for j =2 i +1 . Also, once we have
computed some of these, we can combine them to obtain the values when j is
a sum of powers of 2. This is what happens when we do successive doubling
to reach n . Therefore, we can compute f n ( Q 1 ) /f n ( Q 2 ) quickly. But

div( f n )= n [ P + R ] − n [ R ] − [ nP ]+[ ∞ ]= n [ P + R ] − n [ R ] ,

since nP = ∞ . Therefore, f n is the function f whose values we are trying to
compute, so we have completed the calculation.
The above method can be described in algorithmic form as follows. Let

P ∈ E [ n ]andlet R, Q 1 ,Q 2 be points on E .Let f j be as in (11.8). Define

v j = f j ( Q 1 ) /f j ( Q 2 )

to be the value of f j at the divisor [ Q 1 ] − [ Q 2 ].

1. Start with i = n , j =0, k =1. Let f 0 = 1 and compute f 1 with divisor
[ P + R ] − [ P ] − [ R ]+[ ∞ ].

2. If i is even, let i = i/ 2 and compute v 2 k = f 2 k ( Q 1 ) /f 2 k ( Q 2 )intermsof
v k , using (11.9). Then change k to 2 k , but do not change j .Savethe
pair ( v j ,v k )forthenewvalueof k .

3. If i is odd, let i = i − 1, and compute v j + k = f j + k ( Q 1 ) /f j + k ( Q 2 )in
terms of v j and v k , using (11.9). Then change j to j + k , but do not
change k . Save the pair ( v j ,v k )forthenewvalueof j .

4. If i =0,gotostep2.

5. Output v j .

The output will be v n = f n ( Q 1 ) /f n ( Q 2 ) (this can be proved by induction).

Example 11.6
Suppose we want to calculate v 13 . At the end of each computation, we have
the following values of i, j, k, ( v j ,v k ):

1. i =13 ,j =0 ,k =1 , ( v 0 ,v 1 )

2. i =12 ,j =1 ,k =1 , ( v 1 ,v 1 )

3. i =6 ,j =1 ,k =2 , ( v 1 ,v 2 )

4. i =3 ,j =1 ,k =4 , ( v 1 ,v 4 )

5. i =2 ,j =5 ,k =4 , ( v 5 ,v 4 )

6. i =1 ,j =5 ,k =8 , ( v 5 ,v 8 )