Understanding Montgomery's parameterization of elliptic curves

I'm having a bit of trouble understanding the translation of affine coordinates to projective coordinates in Montgomery curve ECM. Would be very thankful if someone could explain it by expanding the derivation.

From: Speeding the Pollard and Elliptic Curve Methods of Factorization page: 261. $$$$\tag{10.3.1.1}By^2 = x^3 + Ax^2 + x$$$$

Let $$P_1 = (x_1, y_1)$$ and $$P_2 = (x_2, y_2)$$ be two points in the curve, with $$x_1 \neq x_2$$ and $$x_1x_2 \neq 0$$. Then $$P_1 + P_2 = (x_3, y_3)$$ satisfies

$$x_3 = B[(y_1 - y_2)/(x_1 - x_2)]^2 - A - x_1 - x_2,$$ \begin{align}x_3(x_1 - x_2)^2 & = B(y_1 - y_2)^2 - (A + x_1 + x_2)(x_1 - x_2)^2 \\ & = -2By_1y_2 + x_1x_2(x_1 + x_2 + 2A) + x_1 + x_2 \\ & = B(x_2y_1 - x_1y_2)^2/x_1x_2. \end{align}

Similarly, $$P_1 - P_2 = (x_4, y_4)$$ satisfies $$x_4(x_1 - x_2)^2 = B(x_2y_1 + x_1y_2)^2/x_1x_2.$$ Multiply these equations and use (10.3.1.1) to obtain $$x_3x_4(x_1 - x_2)^2 = (x_1x_2 - 1)^2$$ after division by $$(x_1 - x_2)^2$$. This equation remains valid if $$x_1x_2 = 0$$. If $$P_1 = P2$$, a similar derivation yields

$$4x_1x_3(x_1^2 + Ax_1 + 1) = (x_1^2 - 1)^2$$ These equations reference only the $$x_i$$, not the $$y_i$$. Fortunately ECM does not require us to compute the $$y_i$$.

(I don't understand everything below this point. Could someone help me expand these derivations? Seems like it is oversimplified)

Let $$P$$ be an arbitrary point on the curve and let the x-coordinate of $$nP$$ be the rational number $$X_n/Z_n$$. From the ratio $$(X_{m-n}:Z_{m-n}),(X_m:Z_m) and (X_n:Z_n)$$, one can compute the ratio $$(X_{m-n}:Z_{m-n})$$ via the addition formula.

$$X_{m+n} \leftarrow Z_{m-n}(X_mX_n - Z_mZ_n)^2\\ Z_{m+n} \leftarrow X_{m-n}(X_mZ_n - Z_mX_n)^2$$

if $$mP \neq nP$$, and via the duplication formula \begin{align} X_{2n} & \leftarrow (X_n^2 - Z_n^2)^2, \\ Z_{2n} & \leftarrow 4X_nZ_n(X_n^2 + AX_nZ_n + Z_n^2) \end{align}

The costs drop if we store the ratios $$(X_m:Z_m:X_m+Z_m:X_m-Z_m)$$ and rewrite the formulae as (the right sides of the addition formula have been multiplied by 4)

\begin{align} X_{m+n} & \leftarrow Z_{m-n}[(X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n)]^2 \\ Z_{m+n} & \leftarrow X_{m-n}[(X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n)]^2 \\ \end{align} and

\begin{align} 4X_nZ_n & = (X_n + Z_n)^2 - (X_n - Z_n) \\ X_{2n} & \leftarrow (X_n + Z_n)^2(X_n - Z_n)^2 \\ Z_{2n} & \leftarrow (4X_nZ_n)((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n)) \end{align}

• The second part in Projective coordinates. You can see in this question,too. Point addition equation in projective co ordinates – kelalaka Nov 30 '19 at 20:46
• Thanks for the link. Though the answer, seems still a bit far from $X_{m+n}$ above. – einstein Nov 30 '19 at 21:04

Write $$(x_i, y_i) = (X_i : Y_i : Z_i)$$, so that $$x_i = X_i/Z_i$$ and $$y_i = X_i/Z_i$$, where $$Z_i \ne 0$$ is arbitrary. (If you are not familiar with projective coordinates or you like visuals, see an illustration of projective coordinates on a real elliptic curve.)

Let's take the doubling formula for example, where $$(x_3, y_3) = (x_1, y_1) + (x_1, y_1) = [2](x_1, y_1)$$:

$$\begin{equation*} 4 x_1 x_3 ({x_1}^2 + A x_1 + 1) = ({x_1}^2 - 1)^2 \tag{p. 261, second display} \end{equation*}$$

so that

$$\begin{equation*} x_3 = \frac{({x_1}^2 - 1)^2}{4 x_1 ({x_1}^2 + A x_1 + 1)}, \end{equation*}$$

which in projective coordinates is

\begin{align*} \frac{X_3}{Z_3} &= \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 \frac{X_1}{Z_1} \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\ &= \frac{{Z_1}^4}{{Z_1}^4} \cdot \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 \frac{X_1}{Z_1} \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\ &= \frac{\bigl({Z_1}^2\bigr)^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 X_1 Z_1 {Z_1}^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\ &= \frac{\bigl({X_1}^2 - {Z_1}^2\bigr)^2} {4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr)}. \end{align*}

From this, we can read off the numerator and denominator:

$$\begin{equation*} X_3 = \bigl({X_1}^2 - {Z_1}^2\bigr)^2 \qquad\text{and}\qquad Z_3 = 4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr). \end{equation*}$$

Obviously, we can multiply both of them by the same arbitrary nonzero factor too, but there's no need here.

For the addition formula that is not doubling, you're trying to write $$[m + n]P = [m]P + [n]P$$ in terms of $$X$$ and $$Z$$ coordinates for $$[m]P$$, $$[n]P$$, and $$[m - n]P = [m]P - [n]P$$. That is, you have $$x_1 = x([m]P)$$, $$x_2 = x([n]P)$$, and $$x_4 = x([m - n]P)$$, and you're trying to find $$x_3 = x([m + n]P)$$. Use the top equation on p. 261, $$x_3 x_4 (x_1 - x_2)^2 = (x_1 x_2 - 1)^2,$$ and again write it out in terms of $$x_i = X_i/Z_i$$.

The last part is a matter of tidying to reduce the number of distinct intermediate quantities, e.g. using the observation that

$$\begin{multline*} {X_1}^2 + A X_1 Z_1 + {Z_1}^2 = {X_1}^2 - 2 X_1 Z_1 + {Z_1}^2 + 2 X_1 Z_1 + (A/4) 4 X_1 Z_1 \\ = (X_1 - Z_1)^2 + \frac{A + 2}{4} 4 X_1 Z_1 \end{multline*}$$

to write the whole doubling formula in terms of $$X_1 \pm Z_1$$ for a total cost of 4A + 2S + 3M.

• Thanks really appreciate it! – einstein Dec 2 '19 at 20:49

According to the first part (that you understood), you have $$x_3 x_4 (x_1 - x_2)^2 = (x_1x_2 - 1)^2,$$ where $$P_1 = (x_1, y_1)$$, $$P_2=(x_2, y_2)$$, $$P_1 + P_2 = (x_3, y_3)$$ and $$P_1 - P_2 = (x_4, y_4)$$.

In projective coordinate, a point $$(x,y)$$ is represented by $$(X:Y:Z)$$ where $$x=X/Z$$ and $$y=Y/Z$$. And for any $$\lambda \neq 0$$, we have $$(\lambda X: \lambda Y: \lambda Z) = (X:Y:Z)$$ because the equality $$\frac{\lambda X}{\lambda Z} = \frac{X}{Z}$$ holds (same for $$Y/Z$$).

Then, to get the formula with projective coordinates, you replace $$x_3$$ by $$X_3/Z_3$$ and so on with the other coordinates. By playing around, you should get the given formulas.