Using Montgomery ladder to calculate the coordinates In one of my assignments I need to solve the problem below:


  For a Montgomery curve $3y^2 = x^3+x^2+x$ over ${\mathbb{F}}_{11}$ and point $P = (9,8)$, compute the $x$ coordinate of $3P$ using the Montgomery ladder.


I just need a hint to get an idea and not the whole answer. if anyone with some useful links would also be appreciable. As I tried to search google for this but was not able to get any idea.



Is it that I need to find it as $3P = 2P + P $ because I found one question about scalar multiplication here. but then I think it is not the correct way to use the Montgomery ladder.
The Montgomery Curve is introduced by Peter L. Montgomery for speeding up the Pollard and Elliptic Curve Methods of integer factorization. Montgomery Curves are in the form $By^2=x^3+Ax^2+x$ and it is also represented as $M_{A,B}$.

Addition and Doubling Formulas of Montgomery Curves

Given Montgomery Curve $By^2=x^3+Ax^2+x$ and the point $P_1 = (x_1,x_1)$ and $P_2 = (x_2,x_2)$ than the addition and doubling, $P_3 = (x_3,x_3) = P_1+P_2$ as follows


Addition formula in Affine Coordinates: $(P1 \neq \pm P2)$


\begin{align}
\alpha &amp; = (y_2 − y_1)/(x_2 − x_1)\\
x_3 &amp; = B \alpha^2 − A − x_1 − x_2\\
y_3 &amp; = \alpha (x_1 − x_3) − y_1
\end{align}


Doubling formula in Affine Coordinates: $(P1 = P2)$


\begin{align}
\alpha &amp; =  (3x_1^2 + 2 A x_1 + 1)/(2 B y_1)\\
x_3 &amp; = B\alpha^2 − A − 2x_1\\
y_3 &amp; = \alpha (x_1 − x_3) − y_1
\end{align}

As usual, these are calculated from the geometrical meaning of addition.

Montgomery Ladder

The Montgomery Ladder is an algorithm to calculate $[x]P$ for a given scalar $x$ and a point $P$.

Represent $x$ in binary $x= x_0 + 2x_1 + 2^2x_2 + \cdots + 2^mx_m $ and let $m= \lfloor \log_2 x \rfloor$.

  R0 = 0
  R1 = P
  for i from m downto 0 do
     if xi = 0 then
        R1 = point_add(R0, R1)
        R0 = point_double(R0)
     else
        R0 = point_add(R0, R1)
        R1 = point_double(R1)
  return R0


Calculation

Now, $x=3 = 1 + 2\cdot 1$, i.e. $x_0=1$ and $x_1 =1$

$m= \lfloor \log_2 3 \rfloor = 1$. Therefore, we visit the loop twice.

since $x_i =1$ we will be always in the else case, or simply we run the below.

  1. R0 = 0
  2. R1 = P
  3. R0 = point_add(R0, R1)
  4. R1 = point_double(R1)
  5. R0 = point_add(R0, R1)
  6. R1 = point_double(R1)
  7. return R0



$R_0 = \mathcal{O}$
$R_1 = P$
$R_0 = \mathcal{O} + P = P$
$R_1 = P + P = [2]P$
$R_0 = [2]P+P = [3]P$
$R_1 = [2]P+[2]P = [4]P$
return $R_0 = [3]P$


The given Montgomery Curve $3y^2=x^3+x^2+x$ than it is $M_{1,3}$ so $A=1,B=3$ and $P=(9,8)$

$[2]P = (1,10)$ by the below simple sage math point doubling.

k.&lt;a&gt; = GF(11, modulus="primitive")
k.modulus()
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
alpha  =  (3*x1^2 + 2 *A * x1 + 1)/(2 * B * y1)
x3 = B * alpha^2 - A - 2 * x1
y3 = alpha *(x1 - x3) - y1
print x3
print y3


$[3]P = [2]P+P = (5,2)$ by the below simple sage math point addtion.

k.&lt;a&gt; = GF(11)
A = k(1)
B = k(3)
x1 = k(9)
y1 = k(8)
x2 = k(1)
y2 = k(10)
alpha = (y2 - y1)/(x2 - x1)
x3  = B * alpha^2 - A - x1 - x2
y3  = alpha * (x1 - x3) - y1
print x3
print y3




Notes :


One might say that we don't need step 6 since we are not returning it. Keep in mind that that is a need for protection from side-channel attacks.
This ladder algorithm from Wikipedia and it is not an optimal one. See The Montgomery Powering Ladder for a better version.
There is also a full coverage chapter "Montgomery curves and the Montgomery ladder" by Bernstein and Lange to further read.