# Converting a point in a finite field to its real (x, y) coordinate

Let curve $$A = y^2 = x^3 + 3$$ and curve $$B = y^2 \equiv x^3 + 3 \pmod{19}$$

Let $$G$$ be the positive y-valued point in the curve where $$x = 2$$

Let $$r$$ be a random scalar integer, for example, $$r = 5$$

Compute the point $$G*r$$ in both curves $$A$$ and $$B$$

Now, assume I give you the point $$G*r$$ in curve $$B$$, can you find what my point $$G*r$$ in curve $$A$$ is? You don't know the value for $$r$$, but you do know all other parameters. You can't bruteforce the curve.

• You should tell us exactly what the original problem was that led you to this question. Beyond that, there’s a problem, ’cause there is no “the” point in characteristic zero that will correspond to a point with coordinates in $\Bbb Z/16\Bbb Z$. – Lubin Jan 22 at 4:14
• @Lubin its just curiosity. I've also changed the curve which now leads to a group of prime order n=13. – user306666 Jan 22 at 7:41
• I am puzzled by this question. If the coordinates of a point $(x,y)$ are in a finite field, then they are elements of that finite field. They are not real numbers at all. – Jyrki Lahtonen Jan 22 at 7:47
• (cont'd) And I can finally describe why the question is not too well defined. You see, the point $\overline{G}$ on curve $B$ has a finite order, say $\ell$. Meaning that knowing $r*\overline{G}$ does not specify $r$. We have $$r_1*\overline{G}=r_2*\overline{G}$$ whenever $r_1\equiv r_2\pmod{\ell}$. But, more often than not, the points $r_1*G$ and $r_2*G$ are distinct. Basically I am saying that there are infinitely many points on $A$ that become a given point of $B$ when they are reduced modulo $\mathfrak{p}$. – Jyrki Lahtonen Jan 22 at 9:04
• Cross-Posted with Crytpgraphy. This is not considered good in Is cross-posting a question on multiple Stack Exchange sites permitted if the question is on-topic for each site? – kelalaka Jan 22 at 16:05

In the question (as in rev. 3), it can be shown by enumeration that there are 12 solutions to $$y^2 \equiv x^3 + 3\pmod{19}$$ : $$\begin{array}{} (1,2),&(2,7),&(3,7),&(7,2),&(11,2),&(14,7)\\ (1,17),&(2,12),&(3,12),&(7,17),&(11,17),&(14,12) \end{array}$$ Thus with the neutral element $$\infty$$ (aka point at infinity), the order of curve $$B$$ is $$12+1=13$$. The point $$B$$ has the same $$x=2$$ coordinate on curves $$A$$ and $$B$$. We get $$y=\sqrt{11}$$ on $$A$$, and¹ $$y=7$$ on $$B$$.

Point addition $$R\gets P+Q$$ can go by the same formulas for $$A$$ and $$B$$, with addition, multiplication, division², and equality in the field $$\mathbb R$$ for $$A$$, the field $$\mathbb F_{19}$$ for $$B$$:

• If $$P=\infty$$, $$R\gets Q$$.
• Otherwise, if $$Q=\infty$$, $$R\gets P$$.
• Otherwise, if $$x_P\ne x_Q$$ \begin{align} \lambda&\gets\frac{y_Q-y_P}{x_Q-x_P}\\ x_R&\gets\lambda^2-x_P-x_Q\\ y_R&\gets\lambda(x_P-x_R)-y_R \end{align}
• Otherwise, if $$P=Q$$ (that is $$x_P=x_Q$$ and $$y_P=y_Q$$) \begin{align} \lambda&\gets\frac{3{x_P}^2}{2y_P}\\ x_R&\gets\lambda^2-2x_P\\ y_R&\gets\lambda(x_P-x_R)-y_R \end{align}
• Otherwise (that is $$x_P=x_Q$$ and $$y_P\ne y_Q$$), $$R\gets\infty$$.

In order to compute $$G*5$$ on each curve, we can compute $$G_2\gets G+G$$, $$G_4\gets G_2+G_2$$, $$G*5\gets G_4+G$$ per these formulas. Try it online!. We get \begin{align} G*r&=\left(\frac{60503882}{151321},-\frac{141898736429 \sqrt{11}}{58863869}\right)&\text{ on curve }A\\ &\approx(399.838,-7995.14)\\ \\ G*r&=(7,2)&\text{ on curve }B \end{align}

In general, we don't know how to compute $$G*r$$ on curve $$A$$ from $$G*r$$ on curve $$B$$ other than by finding $$r$$ first. If we could, that would³ allow finding $$r$$, which would solve the discrete logarithm problem on a (non-singular) elliptic curve on $$\mathbb F_p$$ in time polynomial w.r.t. $$\log p$$. That feat is widely conjectured impossible with a classical Turing machine, and the basis of the conjectured security of Elliptic Curve cryptography, e.g. on secp256k1.

¹ Finding a modular square root of $$11$$ and taking "positive" as $$\in[0,9]$$. Square roots in the field $$\mathbb F_p$$ can be efficiently computed even when prime $$p$$ is large, see the Tonelli–Shanks algorithm.

² Division $$\frac uv$$ in field $$\mathbb F_{19}$$ can be computed as $$v^{-1}\,u$$ where the modular inverse $$v^{-1}$$ can be found using the extended Euclidean algorithm.

³ If we get the coordinates of $$G*r$$ accurately enough.