# Problem with Elliptic Curve in Montgomery form

I am trying to understand how points are added in Elliptic Curves in Montgomery form. I am working with the curve

$$3y^2 = x^3 + 5x^2 + x \mod 65537$$

Adding the point $(3,5)$ with itself gives (or at least I have calculated, hopefully correctly) $(6117, 1282)$

Now, when I try to check if the point is in the curve solving the curve for $y$: $$y=\pm \sqrt{\frac{x^3 + 5x^2 + x}{3}} \mod 65537$$ I get $y = \pm 14179.763...$ which obviously is different from what I got.

But I have found that if I just calculate each member separatedly $\mod 65537$ I get the same result of $15297$.

My question is: Why is this happening? And, if I can't just calculate y with the 'naïve' way, how should I calculate it, given $x$?

The problem here is that all of the operations you are doing are occurring modulo $65537$, so we have to do them step-by-step. First of all, when working modulo $65537$, "division by 3" really means "multiplication by the inverse of $3$", which is $21846$ because $3 \cdot 21846 \equiv 1 \bmod 65537$. Therefore, $$\frac{(6117)^3 + 5(6117)^2 + (6117)}{3} "=" 21846 \left( (6117)^3 + 5(6117)^2 + (6117) \right) \equiv 5099 \bmod 65537.$$ Now we are left to solve $y^2 = 5099 \bmod 65537$, which is more difficult. A solution $y$ would have to be an integer $0 \leq y < 65537$, so obviously just taking the square root of $5099$ would meaningless since $\sqrt{5099}$ is not an integer. In fact, it is a difficult question to answer the question of when an integer $a$ is a square modulo $m$ (though there are a many results that make it easier, e.g. quadratic reciprocity). The takeaway is that we need a different way to check if the point $(x,y)$ is on the elliptic curve.
The correct way to check whether the point $(x,y) = (6117, 1282)$ is on the curve, then notice that the left-hand side of the defining equation is $$3y^2 = 3(1282)^2 = 4930572 \equiv 15297 \bmod 65537,$$ and the right-hand side is $$x^3 + 5x^2 + x = (6117)^3 + 5(6117)^2 + (6117) \equiv 15297 \bmod 65537.$$
• Okay, so that means that for checking if a point is in a curve I just have to compute each member $\mod 65537$ and compare. And that for calculating $y$ I should calculate the quadratic residue. Thanks! – Noxbru Aug 14 '15 at 10:16
Take a simpler example, without elliptic curves: $2 = 3^2 \mod 7$; and $\sqrt 2 =1.41...$ (as a real number), but $3 = \pm 1.41... \mod 7$ doesn't make much sense. The reason, one could say, is that the decimal expansion, which expresses convergence of a certain sequence in the reals, does not in general play well with congruences - and while $\mathbb R / 7\mathbb Z$ makes sense as an abelian group, it doesn't as a ring.