Problem with Elliptic Curve in Montgomery form

Question

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$?

Answer 1

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

Answer 2

To add to @msteve's answer...

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.

To answer your question "how to find square roots mod p?", I looked in https://en.wikipedia.org/wiki/Quadratic_residue - and at the section "prime or prime power modulus" for references.