# 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.

• Do you know what the Montgomery ladder algorithm is? – poncho Jan 16 '16 at 1:57
• Yes I have read about it and I know that we double when we have bit 1 and we add if bit 0. But I am not able to apply here. Or otherwise I haven't that much knowledge about it. – TechJ Jan 16 '16 at 1:59
• – poncho Jan 16 '16 at 4:58

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 & = (y_2 − y_1)/(x_2 − x_1)\\ x_3 & = B \alpha^2 − A − x_1 − x_2\\ y_3 & = \alpha (x_1 − x_3) − y_1 \end{align}

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

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

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

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
R0 = point_double(R0)
else
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
4. R1 = point_double(R1)
6. R1 = point_double(R1)
7. return R0

1. $$R_0 = \mathcal{O}$$
2. $$R_1 = P$$
3. $$R_0 = \mathcal{O} + P = P$$
4. $$R_1 = P + P = P$$
5. $$R_0 = P+P = P$$
6. $$R_1 = P+P = P$$
7. return $$R_0 = 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)$$

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

k.<a> = 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


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

k.<a> = 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 :