# 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, 2020 at 5:34
• @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, 2020 at 23:44
• Note that, Andreas's book is not a good source to learn elliptic curves, since they use EC multiplication instead of EC scalar multiplication that confused many How do I multiply two points on an elliptic curve? Jan 27 at 18:08
• You should accept the dupe when see it, this is the way of our site. It is good on the non-math side. The math side really depends on you. If you need Hash functions, Elliptic Curves, Digital signatures like ECDSA, I suggest Serious Cryptography: A Practical Introduction to Modern Encryption Jan 28 at 9:59
• Another good cryptography book is Katz and Lindell's "Introduction to Modern Cryptography", and for bitcoin maybe "Grokking Bitcoin" by Rosenbaum? Jan 28 at 10:05

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

The curve used by bitcoin is secp256k1, which has the equation $$y^2 = x^3 + 7$$

That means every single point $$P = (x, y)$$ on the curve must satisfy this equation.

So, given $$x$$, we can compute the right hand side of the equation $$x^3 + 7$$ to obtain $$y^2$$. Then we need to "square root" this in the field $$F_p$$ to find $$y$$. Note that is not the same as taking the square root of a real number.

We shall require that $$p \equiv 3 \pmod{4}$$, which is true of the prime $$p$$ ($$= 2^{256} - 2^{32} - 977$$) which is used in secp256k1. The way to compute this "square root" of an element $$a$$ in $$F_p$$, when $$p \equiv 3 \pmod{4}$$, is to use the equation: $$y = a^{(p+1)/4} \pmod{p}$$

You can check that this is true because suppose $$a = y^2$$. then $$\left( a^{(p+1)/4} \right)^2 \equiv a^{(p+1)/2} \equiv y^{p+1} \pmod{p}$$ and then, by Fermat's little theorem: $$y^{p+1} \equiv y^2 \equiv a \pmod{p}$$

Your example is not great, because $$10^3 + 7 \equiv 0 \pmod{19}$$. So $$y = 0$$ is a trivial square root.

Using a different example, let's work over $$F_{23}$$, with $$p = 23$$, and keep the same value of $$x = 10$$. Then $$10^3 + 7 \equiv 18 \pmod{23}$$. Now, to compute $$y$$ such that $$y^2 \equiv 18 \pmod{23}$$, we use the above equation: $$y = 18^{(23+1)/4} = 18^6 \equiv 8 \pmod{23}$$

To confirm this, we can check that $$8^2$$ does indeed equal $$18$$ modulo 23. So the point we are looking for is $$(10, 8)$$. Note too that there is the "negative" version of the point with the same x-coordinate, $$(10, -8) \equiv (10, 15)$$, because $$y^2 = (-y)^2$$. We can check this too, because $$15^2 \equiv 18 \pmod{23}$$ as expected.

Note that not all $$x$$ values will have a valid corresponding $$y$$ value. We expect roughly half the possible choices of $$x$$ to correspond to (usually) two points each. When $$a = x^3 + 7$$ does indeed have a corresponding $$y$$ value such that $$y^2 = a$$, then we say a is a quadratic residue modulo $$p$$.

• Thank you really much for your detailed explanation, I have been doing searches about this at got stuck at the part everyone mentioned about the condition p mod 4 = 3. I am curious about how that requirement came up in the first place? Like to make the function easier to solve or something similar? Jan 28 at 9:26
• Yep, it makes it a lot easier. In the general case, we need to use the Tonelli-Shanks algorithm. It is still doable, of course, just a bit more complicated. Jan 28 at 10:01