I was trying to implement the double and addition formulas for elliptic points on a Montgomery elliptic curve. I came across this weird thing which should definitely not be happening.

I took a point $P_1$, and doubled it twice. This should be $4P_1$. Let's call this point $P_4'$.

Next I doubled $P_1$ to get $P_2$. Then carried out $P_1 + P_2$ to get $P_3$, and then again added $P_3$ and $P_1$ to get $P_4$.

Now I was expecting both these points to be the same, since both are simply $4$ times $P_1$.

For example, let us take a curve $y^2 = x^3 + 6x^2 + x$ (Montgomery Curve), over $F_{2425967623052370772757633156976982469681}$

Let a point $P_1$ be $[2 :: 1]$ (projective coordinates, $y$ dropped)

Doubling this twice, gives the point $[339112225 :: 126909216]$ ($P_4'$).

Adding it stepwise to reach $4P_1$, gives the point $[106258781030400 :: 39766241378304]$

Question: Shouldn't $P_4$ be equal to $P_4'$ ? Since both are equal to $4P_1$?

I am using the following formulas for addition and doubling.

$$X_{m+n} = (z_{m-n}\cdot((x_m - z_m)\cdot(x_n + z_n) + (x_m + z_m)\cdot(x_n - z_n))^2 \mod{n})\\ Z_{m+n} = (x_{m-n}\cdot((x_m - z_m)\cdot(x_n + z_n) - (x_m + z_m)\cdot(x_n - z_n))^2 \mod{n})\\ X_{2n} = (((x_n + z_n)^2)\cdot((x_n - z_n)^2) \mod{n})\\ Z_{2n} = ((4\cdot x_n\cdot z_n)\cdot((x_n - z_n)^2 + {a+2\over4}\cdot 4\cdot x_n\cdot z_n) \mod{n})$$

These formulas were mentioned here http://en.wikipedia.org/wiki/Montgomery_curve

I have implemented a python version of the addition and double, and carried out the above arithmetic in this piece of code.

http://ideone.com/w68cKC

  • 1
    Note that you can't have such point in the given field, as $2^3+6\cdot 2^2+2=34$ is a quadratic non-residue (WA) given modulo. If this matters, though. – Alexey Burdin Jun 5 '15 at 15:49
  • 1
    Also note that $\dfrac{106258781030400}{39766241378304}$ $= \dfrac{339112225}{126909216}$ i.e. it's exactly the same point. – Alexey Burdin Jun 5 '15 at 15:55
  • It was really silly of me not to notice that. I had been stuck on it for quite some time now, thanks a lot! – Kushagra Singh Jun 5 '15 at 15:58

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.