2
$\begingroup$

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.

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

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}$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nayuki Aug 24 '15 at 16:16
  • $\begingroup$ @NayukiMinase: I am happy to hear that. And the statistics are plausible, given Hasse's theorem on $\#E(\mathbb{F}_p)$. $\endgroup$ – ccorn Aug 24 '15 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.