1
$\begingroup$

Can someone please explain to me why don't we need the y-coordonnate in projective form, and what does this $Z_{m−n}$ in the following formulas mean (from Wikipedia) ? How can we get this value ?

$X_{m+n} = Z_{m−n}((X_m - Z_m)(X_n+Z_n)+(X_m + Z_m)(X_n-Z_n))^2$

Moreover, i would like to know why does the wikipedia article say that "there is no distinction between the affine points $( x , y )$ and $( x , − y )$ because they are both given by the point $( X : Z )$", whereas the projective coordonnates represent the lines of the plane passing through $(0,0)$ , and the lines passing through $((0,0) , (x,y))$ and $((0,0) , (x,-y))$ are not the same for me.

Thank you.

$\endgroup$
  • $\begingroup$ It looks like the points in Montgomery form are specified by only the $x$ coordinate $(X:Z)$, so although $(x,y)$ and $(x,-y)$ are different points they become indistinguishable using the $(X:Z)$ representation. You can solve for the $y$-coordinate(s) from the equation for the curve given the $x$ coordinate. $\endgroup$ – sharding4 May 31 '17 at 12:17
  • $\begingroup$ For a given point $P$ the notation $X_n$ represents the first coordinate of the point $[n]P$ in projective coordinates while $Z_n$ represents the last coordinate. $Z_{m-n}$ is the third coordinate of the point $[m-n]P$. $\endgroup$ – sharding4 May 31 '17 at 12:24
2
$\begingroup$

The projective coordinate pair $(X_n:Z_n)$ identifies the set of the two points $P_{\pm n}=\pm nP_1=nP_{\pm1}$. The set of the omitted projective coordinates $\{\pm Y_n\}=\{Y_{\pm n}\}$ is implicitly determined by the curve equation. The important point is that if $nP_1=O$, then $-nP_1=O$ as well, and $O$ is unambiguously identified with $(X_O:Z_O)=(0:0)$.

Adding $P_{\pm m}$ and $P_{\pm n}$ determines the set $\{P_{\pm(m+n)},P_{\pm(m-n)}\}$, but you cannot tell which two-point subset is which unless you already know one two-point subset and therefore can deduce the other. This is what happens here: By keeping track of $(X_{m-n}:Z_{m-n})$ besides $(X_n:Z_n)$ and $(X_m:Z_m)$, Montgomery uniquely deduces $(X_{m+n}:Z_{m+n})$.

In the binary Montgomery ladder algorithm, $|m-n|=1$, so $(X_1:Z_1)$ needs to be kept around. Each ladder step then computes the pair $\bigl((X_{2n}:Z_{2n}),(X_{2n+1}:Z_{2n+1})\bigr)$ or $\bigl((X_{2n+1}:Z_{2n+1}),(X_{2n+2}:Z_{2n+2})\bigr)$ from the pair $\bigl((X_n:Z_n),(X_{n+1}:Z_{n+1})\bigr)$: One $(X:Z)$ entry of the latter pair gets replaced by that for the point sum $(X_{2n+1}:Z_{2n+1})$, thereby involving $(X_1:Z_1)$; the other entry is subjected to point doubling, thereby involving the curve parameter $A$.

References:

  1. Montgomery: Speeding the Pollard and Elliptic Curve Methods of Factorization, Mathematics of Computation, Volume 48. Number 177, January 1987, pages 243–264
$\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.