Join Log in
Score:0
avatar Crypto

Two Elliptic Curve Points having the Same X coordinate

ua flag
trijia

Suppose in a elliptic curve (say the curve equation is: $y^2 = x^3 -17$) with prime order $q$, we have $(x,y_1) = nP$, where $P$ is a generator and $n<\lceil{q/2}\rceil$. Can we claim that there does not exist $n' < \lceil{q/2}\rceil$, such that $(x,y_2)=n'P$ is a valid curve point where $y_2 \neq y_1$?

149
0 + 0
fgrieu avatar
ng flag
fgrieu
For [Dr. Spock](https://en.wikipedia.org/wiki/Spock), answer to question as worded in [revision 6](https://crypto.stackexchange.com/revisions/96275/6) is still **No**. If $(x,y_1) = nP$, where $P$ is a generator and $n<\lceil q/2\rceil$, then $n'=n-2\,(n\bmod q)$ also verifies $n'<\lceil q/2\rceil$, and $(x,y_2)=n'P$ is a valid curve point where $y_2\neq y_1$. The catch is that the question allows negative $n'$ and $n$. The [accepted answer](https://crypto.stackexchange.com/a/96286/555) correctly restricts $n$ and $n'$ to be positive, making Yes correct.
0
Reply
Score:3
poncho avatar Crypto
my flag
poncho

Can we claim that if $n < \lceil{q/2}\rceil$, then there do not exist $y_2 \neq y_1$ such that $(x,y_2)$ is a valid curve point?

No, such a claim would be false. If $(x, y_1)$ is a valid point, that is, if $y_1^2 = x^3 - 17$, then $(x, q-y_1)$ is also a valid point. Hence, unless $y_1 = 0$, there will always be a second point with the same $x$ coordinate.

0 + 0
Daniel S avatar
ru flag
Daniel S
I'm not certain whether the question is intended to be whether or not there exists $(x,y_2)=n'P$ with $n'<\lceil q/2\rceil$. In this case there is not such a solution as $(x,y_2)$ will be equal to $(q-n)P$ and $q-n>\lceil q/2\rceil$.
2
Reply
fgrieu avatar
ng flag
fgrieu
Ah, the dilemma: answering the question asked, or what the OP wanted to ask?
1
Reply
ua flag
trijia
@Daniel S yes that is what I meant, edited the question. How can we show that $(q-n)P = (x,y_2)$ when $nP=(x,y_1)$?
0
Reply
Score:1
Daniel S avatar Crypto
ru flag
Daniel S

Yes. Fix the $x$ co-ordinate and let $c=x^3-17$. The equation $y^2\equiv c\pmod p$ has at most two solutions (it will have zero if $c$ is a quadratic non-residue, two if $c$ is a quadratic residue and one if $c\equiv 0\pmod p$). If it has two solutions $y_1$, $y_2$ they will be additive inverses: $y_1\equiv -y_2\pmod p$. In the standard formulation of the elliptic curve group (taking the point at infinity as the identity), two points are inverses of each other on the curve if and only if they have the same $x$ coordinate and $y$ coordinates additive inverses. This means that $(x,y_1)+(x,y_2)=\mathcal O$. We rewrite this as $nP+n'P=(n+n')P=\mathcal O$ and conclude that $n+n'\equiv 0\pmod q$. This tells us that $n'\mod q=q-n$. We now note that $0<n<\lceil q/2\rceil\iff q>q-n>\lceil q/2\rceil$.

0 + 0
Score:0
Fractalice avatar Crypto
in flag
Fractalice

If $P = (x,y)$ has order $q$, then $$(q-1)P = -P = (x,-y).$$ When $q=2$ (equivalently, $y=0$), these two points coincide: $P=-P$.

0 + 0
ธงชาติไทย
Elon Musk
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.