# Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

Given an x-coordiante of a point on the SECP256K1 curve, is it possible to calculate the corresponding y-coorindate? (Assuming the point is a verifying public key that complies with the Bitcoin standards.)

I am new to the cryptographic realm so please forgive me if the question is naive. From what I know, the public key is a point, or a pair of integers. The SECP256K1 curve is a curve where any point (x, y) on it satisfies

(y ** 2) mod p == (x ** 3 + 7) mod p


where p = 2**256 - 2**32 - 977.

Now let's confine the discussion within the Bitcoin scope. Assume we have a private key that complies with the Bitcoin standards, and from it we can derive the public key, which can be represented as a point (x, y) on the SECP256K1 curve.

Now given only such a x, is it possible to calculate the y?

As a real example, given only x as

0x6778ec0abf66f1ba4d93aa45cad77dc26c593f520448f6fff5b70357270154ba


is it possible get the y as

0x6a5e8cd7276f80ee2f7c081702eff3e14134b006acd0afc8467be94a0a3a0558

• SEC#1 from secg.org explains it in section 2.3.4. Octet-String-to-Elliptic-Curve-Point Conversion. Jul 22 '20 at 5:34
• Thanks for pointing to the right direction. The key part is an efficient algorithm to compute the modular square root, namely the Tonelli–Shanks algorithm, which I didn't know and I was asking for, and which I know now. If time permits I can make an answer my own. Jul 22 '20 at 7:13
• Note that the linked strategy requires an extra byte (or rather 2 bit) of information as there are two possible $y$ values for each $x$.
– SEJPM
Jul 22 '20 at 10:22
• In the compression form, the value of $g$ starts with 02 or 03, '02' tells to select the root whose least significant bit is even, and versa. Jul 22 '20 at 14:40
• @MaartenBodewes: 01 is not used; 00 is infinity aka $O$ and 04 is uncompressed. X9.62 used 06 and 07 for hybrid, but SEC1 and AFAIK everybody else just ignored hybrid as being silly and useless. Jul 22 '20 at 23:44

Given an $$x$$-coordinate of a point on the SECP256K1 curve, is it possible to calculate the corresponding $$y$$-coordinate?

Yes, if there exists such $$y$$ for the given $$x$$. And, absent other indication, such $$y$$ can only be found within sign (or equivalently, parity). That limitation is because if $$y^2\equiv x^3+7\pmod p$$ with $$p=2^{256}−2^{32}−2^{10}+2^6-2^4−1$$ as in secp256k1 has a solution $$y_0$$ in $$[0,p)$$, then $$y_1=p-y_0$$ also is a solution.

Note: in some cases including secp256k1 as used in Bitcoin, a public key with $$x$$ and without $$y$$ (that is, in compressed form) comes with a prefix of 02 if $$y$$ is even, 03 if $$y$$ is odd, and that allows to fully recover $$y$$.

By Euler's criterion, $$x^3+7$$ has a square root modulo $$p$$ if and only if $$(x^3+7)^{(p-1)/2}\bmod p=1$$. That holds for the question's $$x$$, thus there are solutions.

In the general case, the Tonelli–Shanks algorithm can be used to find modular square roots. Since $$p\equiv3\pmod4$$, that algorithm reduces to computing $$y_0\gets (x^3+7)^{(p+1)/4}\bmod p$$ and $$y_1\gets p-y_0$$. The question's $$y$$ happens to be $$y_1$$.

Justification: when we have checked $$(x^3+7)^{(p-1)/2}\bmod p=1$$, and computed $$y_0$$ as $$(x^3+7)^{(p+1)/4}\bmod p$$, the later is such that $$\begin{array}{} {y_0}^2 &\equiv&\left((x^3+7)^{(p+1)/4}\right)^2 &\pmod p \\ & \equiv&(x^3+7)^{(p+1)/2} &\pmod p \\ &\equiv&(x^3+7)^{(p-1)/2}\,(x^3+7)&\pmod p\\ &\equiv&x^3+7 &\pmod p & \text{since}\;(x^3+7)^{(p-1)/2}\bmod p=1\end{array}$$ thus $$y_0$$ is a solution to $$y^2\equiv x^3+7\pmod p$$.

Definitions: $$\begin{array}{l} u\equiv v\pmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\\ u=v\bmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\;\text{ and }0\le u