Find point on Elliptic Curve

Question

I want to program the points on elliptic curves $\mod p$, for certain $p$ prime in Python. For this I want for given $p$, $a \pmod p$ and $b \pmod p$ to find $x \pmod p$ and $y \pmod p$ such that: $$y^2 \equiv x^3 + ax + b \pmod p$$ Is there a formula for finding (just one!) specific $(x,y) \in (\mathbb{Z_p},\mathbb{Z_p})$ on this curve. Then I can just implement this.
Alternatively: is there a very fast algorithm to find a solution (even when $p=22801763489$ for example). Running first over all $(0,y)$, then $(1,y)$ for the equation doesn't do the trick.

Answer 1

• Step 1: pick $x_0 \bmod p$ and compute $f=x_0^3+ax_0+b$.
• Step 2: compute the Legendre symbol $L(x_0)=\left(\frac{f}{p}\right)$. This should be "fast" using quadratic reciprocity and other such results about Legendre symbols. If $L(x_0)=0$ or $-1$, then return to Step 1 and pick a different value of $x_0$.
• Step 3: compute a quadratic residue $y_0$ for $f$, i.e., find $y_0\bmod p$ such that $y_0^2 \equiv f \bmod p$, using a method such as Cipolla's algorithm or Tonelli-Shanks' algorithm.

The point $(x_0,y_0)$ is on $E$.