Score:1

Projective coordinates for Montgomery curves

tt flag

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?

Score:1
my flag

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.

filippo polidori avatar
bf flag
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$?
poncho avatar
my flag
@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$)
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.