# Montgomery Ladder with affin/projective Coordinates

So I'm trying to understand why the montgomery arithmetic is fast and what the montgomery ladder is.

With this Post i understood the basic affin arithmetic and Ladder.

So this is not really faster than arithmetic on common weierstrass equations. In the original Paper from Montgomery, he defined the projective arithmetic for adding and doubling.

My first questions are: Is the projective arithmetic faster because of not having a division? Does the ladder have constant time, because there is not division? Does that mean, that the ladder with affine coordinates don't have constant time? ( My idea is, that division in a field is a multiplication with a inverse. For calculating an inverse you need the euklidiean algorithm. This algorithms is not the fastest and can't be computed in constant time)

Then i was looking into the work of Bernstein. In this Paper and in his Curve25519 he describes a optimized double and add formula. It looks like this:

When i get it right, you can use the montgomery ladder for affine coordinates with the affine arithmetic and for projective coordinates with the projective coordinates. So Bernstein made the shown graph for the projective montgomery ladder in order to give an optimized implementation, where already computed results are used again. So i tried to write the graph into Pseudocode:

R0 = (0,0)
R1 = (x,y)
x1 =
for i from m downto 0 do:
if xi = 0 then:
x,z,x',z' =  R0[0], R0[1], R1[0], R1[1]
tmp1, tmp2 = x, x'

x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
tmp1, tmp2 = x, x'

x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

z = z*( tmp1 + ((A-2)/4)*z )
x' = x' * x'
z' = z' * z' * x1

R0[0], R0[1], R1[0], R1[1] = x, z, x' , z'
else
x,z,x',z' =  R1[0], R1[1], R0[0], R0[1]
tmp1, tmp2 = x, x'

x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
tmp1, tmp2 = x, x'

x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

z = z*( tmp1 + ((A-2)/4)*z )
x' = x' * x'
z' = z' * z' * x1

R0[0], R0[1], R1[0], R1[1] = x',z',x, z
return R0


That brings me to my next questions: Where is the x1 comming from, how is it calculated? I saw in his paper, that x1/z1 = X(Q - Q'), but it remains unclear how to substract those points.

Next question is: Is this peudocode logical correct ( at least everything except the x1)?

I hope this are not too many questions!

2. Question: With projective coordinates it is only possible to add/double multiples of the same point. The montgomery ladder starts with a given scalar $$n$$ and Point $$P$$. In each step two results are calculates $$R0$$ and $$R1$$. The important point here is, that those results are either of the form $$(n')R0$$, $$(n'+1)R1$$ or $$(n'+1)R0$$, $$(n')R1$$. That means the difference between them is always 1. (When you look at the definition for the projective Arithmetic it is clear what that means). For the ladder this means, that $$x1$$ is always the x coordinate of the starting Point $$P$$. Therefore it is always the same and must not be computed!