Finding 1 solution of $(x^3 + ax + b) \bmod p = 0$

Question

I am writing unit-tests for an elliptic curve implementation (secp256r1 / prime256v1) and need to find a curve point with $y = 0$ to reach coverage for an edge case (special handling of curve points with $y = 0$ during point doubling).

The curve is defined as

$$ y^2 \bmod p \equiv x^3 + ax + b \bmod p $$

with p, a and b being fixed constants

$$ p=115792089210356248762697446949407573530086143415290314195533631308867097853951 $$

$$ a=115792089210356248762697446949407573530086143415290314195533631308867097853948=-3 \mod p $$

$$ b=41058363725152142129326129780047268409114441015993725554835256314039467401291 $$

and I must find

$$ 0 \bmod p \equiv x^3 + ax + b \bmod p $$

I would appreciate your help. If you know a solution or a database (I think this is a common edge case for this named elliptic curve), please let me know :)

Best regards, Dustin

Answer 1

If $P=(x,0)\in E$ for some $x$, then $-P=(x,-0) = (x,0) = P$, hence

$$P+P={\cal O}_E$$

The algorithm for adding points would first check whether you are trying to add $P$ to $-P$, and if so (which is the case for such specific $P$), return ${\cal O}_E$. Hence, the algorithm would never enter the usual computation of $2P$ that requires the computation of $$\lambda = \dfrac{3x_P^2+a}{2y_P}$$

So when computing $\lambda$, it holds that assert (y != 0), and you'll never succeed in covering the computation of $\lambda$ with $y=0$ (except there is a bug elsewhere in the code).

Answer 2

Mathematica does not find any solutions to the equation $x^3-3x+b=0$ in the field $\Bbb{F}_p$. This is just as well because the order of this curve $n$, see page 16 of the linked document, is an odd integer. When the cofactor $h=1$, the order of $G$ is the order of the curve. But for a curve in the short Weierstrass form, a point with $y=0$ would be of order two, implying that $2\mid n$ by Lagrange's theorem.