1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Noxbru Aug 14 '15 at 10:16
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.