# Solve for $x$ in elliptic curve $y^2 = x^3 + ax + b$

Given $y$, is it possible to solve for $x$ in the elliptic curve equation $y^2 = x^3 + ax + b$ over a finite field?

Or is it known to be as difficult as say, something like the discrete logarithm problem via a reduction argument?

Specifically I would like to know this for the secp256k1 curve over field = $\mathbb{Z}_p$, with:
modulus $p = 2^{256} - 2^{32} - 977$; $a = 0$; $b = 7$;
order of base point = $2^{256} - 432420386565659656852420866394968145599$.

(The curve equation is simply $y^2 = x^3 + 7$.)

Note: Because the field has the property that $p \not\equiv 2 \!\! \mod \! 3$, it's not possible to compute a cube root via a simple exponentiation by Fermat's little theorem.

Side note: The opposite is feasible; given $x$ it is easy to calculate the two possible values of $y$ on this elliptic curve.

• Solve for arbitrary $a$ and $b$? – Michael Galuza Jul 25 '15 at 3:17
• Covering the secp256k1 case is sufficient for my purposes. – Nayuki Jul 25 '15 at 3:18

This answer is for the concrete values of $p,a,b$ given in the question; it relies on $p\equiv 7\pmod{9}$, $a=0$, $\left(\frac{b}{p}\right)=-1$.

The key property is that $p-1$ is divisible by $3$, but not by $3^2$. Instead $p+2$ is divisible by $3^2$. This allows us to follow an approach for cuberoots analogous to the one used for finding squareroots when $\frac{p-1}{2}$ is odd.

Set $g$ to a primitive root modulo $p$. Here, $g\equiv 3\pmod{p}$ works. Then $\rho = g^{(p-1)/3}$ is a primitive 3rd root of unity in $\mathbb{F}_p$. The other one is $\rho^2 = -1 - \rho$.

Suppose $(x,y)$ is a point on the curve with given finite $y$, thus $y^2 = x^3 + b$. Set $c = y^2 - b$. Then $c\not\equiv 0\pmod{p}$ because the given $b=7$ has $\left(\frac{b}{p}\right)=-1$, thus $b$ is a nonsquare modulo $p$. So we have a nonzero $c = x^3$, therefore $$c^{(p-1)/3}\equiv1\pmod{p}$$ If you cannot trust that $y$ really belongs to a point on the curve, you might want to check that.

Set $x_1 = c^{(p+2)/9}$. Then $x_1^3\equiv c^{(p+2)/3}\equiv c^{(p-1)/3}c\equiv c \pmod{p}$, so $x_1$ is a candidate for $x$ in the sense that $(x_1,y)$ is in the curve. The other candidates are $x_2 = x_1\rho$ and $x_3 = x_1\rho^2 = -x_1 -x_2$. No more points with the given $y$ exist because we are working in a field, so an equation of degree $d$ can have at most $d$ solutions.

Basically we have used the fact that $p-1$ is divisible by $3$ only once, hence the order of $c$ in $(\mathbb{Z}/p\mathbb{Z})^\times$, call it $m$, must be coprime to $3$. Therefore there exists a multiplicative inverse $k$ of $3\pmod{m}$, and $c^k$ effectively gives a cuberoot of $c$. (Of the three possible cube roots, $c^k$ gives the one that is itself a cube.) For $p\equiv 7\pmod{9}$ we have found $k=\frac{p+2}{9}$; if $p$ were congruent to $4\bmod{9}$ instead, we would find $k=\frac{2p+1}{9}$.

• Thanks! I've implemented your algorithm and it works. Specifically I implemented $\rho$ and $x_1 = c^{(p+2)/9}$. I can see that for a random sample of $y$ values, only about 1/3 of them have any solution for $x$ at all. And of course when there's a solution, there are 3 solutions. – Nayuki Aug 24 '15 at 16:16
• @NayukiMinase: I am happy to hear that. And the statistics are plausible, given Hasse's theorem on $\#E(\mathbb{F}_p)$. – ccorn Aug 24 '15 at 17:16