1
$\begingroup$

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. $$\begin{equation}\tag{10.3.1.1}By^2 = x^3 + Ax^2 + x\end{equation}$$

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}$$

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

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.

$\endgroup$
  • $\begingroup$ Thanks really appreciate it! $\endgroup$ – einstein Dec 2 '19 at 20:49
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.