# Projective coordinates for Montgomery curves

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?

## 1 Answer

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.

• 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$? Feb 6, 2023 at 10:03
• @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$) Feb 6, 2023 at 13:42