Some confusions about Repeated Doubling Algorithm?

Question

The following repeated point doubling algorithm is taken from the book Guide to Elliptic Curve Cryptography by D. Hankerson, A. Menezes, and S. Vanstone on page#93.

Clearly, this algorithm is better than calling the point doubling procedure $m$ times. But I am having a hard time to understand the correctness of this algorithm. So, I have two questions about the use of $2Y$ instead of $Y$ coordinate after the first iteration in the body of the loop

1) How to prove that it computes the correct value of all the coordinates at the end?

2) How to prove that it computes $2Y$ for $4P$ and so on?

Answer 1

This algorithm is a small optimization to Algorithm 3.21 of the same book on page 91. Algorithm 3.21 is the original algorithm for computing elliptic curve doubling using Jacobian coordinates (with $a=-3$). If you have a close look at both of the algorithms, you will notice many similarities. For example, Algorithm 3.21 computes $A \leftarrow 3(X_1-Z_1^2)(X_1+Z_1^2)$, whereas Algorithm 3.23 computes $A \leftarrow 3(X^2-W)$ (note that $W=Z^4$!). Therefore I would suggestion breaking problem (1) down into two parts:

1. For $m=1$ prove that Algorithm 3.23 computes the same thing as Algorithm 3.21. Since we are using Jacobian coordinates, this means showing that $X_3/Z_3^2=X/Z^2$ and $Y_3/Z_3^3=(Y/2)/Z^3$ (using the notation of the respective algorithms, and of course with equal input).
2. Use induction to prove the result for $m>1$.

I am not sure whether I understand part (2) of your question correctly. The statement $2Y$ for $4P$ is not really well-defined. Since we are working with projective coordinates (Jacobian), what you would probably want to check is whether we are computing a $X,Y,Z$ such that $4P=(X/Z^2 : (Y/2)/Z^3: 1)$. Since the first part of your question proves that the algorithm correctly computes $2^mP$ for any $m>1$, the second statement follows by applying the definition of Jacobian coordinates to Line 4 of Algorithm 3.21.