1
$\begingroup$

I have this Montgomery curve $y^2=x^3+10x^2+x \mod 83$ and a point $Q(3,28)$, doubling this point in affine coordinates I get $2Q(61,35)$.

Switching to projective coordinates I know that $x = X/Z$ and $y = Y/Z$ and $Z = 1$ at the beginning so $Q(3,28,1)$, following the Wikipedia formulas for doubling in projective coordinates, I get $X_2p = 64$ and $Z_2p = 65$.

How do I verify that this point in projective coordinates belongs to the curve? Do I need the $y$-coordinate in projective coordinates? If so, how do I calculate it?

$\endgroup$

1 Answer 1

1
$\begingroup$

How do I verify that this point in projective coordinates belongs to the curve?

Assuming that you don't have the $y$ coordinate, then the requirement on $x$ is that $x^3 + 10x^2 + x$ is a quadratic residue; that is, there exists a $y$ such that $y^2$ is that value.

Now, you have the projective coordinates; the corresponding requirement is that:

$$(Y/Z)^2 = (X/Z)^3 + 10(X/Z)^2 + (X/Z)$$

Multiplying both sides by $Z^4$, we get

$$(YZ)^2 = X^3Z + 10X^2Z^2 + XZ^3$$

The lhs is a square (and by selecting the correct $Y$, can be any square, assuming $Z \ne 0$), and so the condition is that $X^3Z + 10X^2Z^2 + XZ^3$ is a quadratic residue.

I believe that testing this value for quadratic residuosity will be cheaper than recovering the possible $y$ values.

$\endgroup$
2
  • $\begingroup$ You wrote: The lhs is a square (and by selecting the correct Y,can be any square, assuming Z≠0), and so the condition is that $X^3Z+10X^2Z^2+XZ^3$ is a quadratic residue. What would be the formula for calculating $Y$ if I wanted to convert the point $Q2$ from projective coordinates to affine coordinates? For the $x$-coordinate there is no problem, I know that $x$ = $X*Z^-1$ and I get exactly $61$, but how would I get $y$ = $35$? $\endgroup$ Feb 6, 2023 at 10:03
  • $\begingroup$ @filippopolidori: the most straight-forward way to compute $Z^{-1} = 23$ and $x = XZ^{-1} = 61$ (which you have done), and then compute $y^2 = x^3 + 10x^2 + x = 63$, and then squareroot $y^2$; because $83 \equiv 3 \pmod 4$, the straight-forward $(y^2)^{(p+1)/4} = 48$ works; remember, $-48 = 35$ is also a valid y-coordinate (because it is also a square root of $y^2$) $\endgroup$
    – poncho
    Feb 6, 2023 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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