How do you systematically find all points on an elliptic curve $y^2 \equiv x^3 + ax + b \mod p$?

For each $x$ from 0 to $p-1$: compute $x^3 + ax + b \mod p$, then check if the result is a quadratic residue (has a square root mod p). If yes, there are two points $(x, y)$ and $(x, p-y)$. Don't forget the point at infinity.

* Over $\mathbb{F}_7$ the eight affine points pair up as $(x,y)$ and $(x,7-y)$ around $y=3.5$; with the point at infinity that makes group order 9. *

Step-by-step method:

1. Build a table of $x^3 + ax + b \mod p$ for every $x \in \{0, 1, ..., p-1\}$
2. Build a table of $y^2 \mod p$ for every $y \in \{0, 1, ..., p-1\}$
3. For each $x$: check if $x^3 + ax + b$ appears in the $y^2$ table
   • If yes → two points: $(x, y)$ and $(x, p-y)$ (unless $y = 0$, then just one)
   • If no → no point with this x-coordinate

Example: $y^2 \equiv x^3 + 3x + 2 \mod 7$

Quadratic residues mod 7: $\{0, 1, 2, 4\}$. Check each x:

• $x=0$: 2 is a QR → $y^2=2$ → $y \in \{3, 4\}$ → points $(0,3), (0,4)$
• $x=2$: 2 is a QR → $y^2=2$ → $y \in \{3, 4\}$ → points $(2,3), (2,4)$
• $x=4$: 1 is a QR → $y^2=1$ → $y \in \{1, 6\}$ → points $(4,1), (4,6)$
• $x=5$: 2 is a QR → $y^2=2$ → $y \in \{3, 4\}$ → points $(5,3), (5,4)$
• $x=1, 3, 6$: values $6, 3, 5$ are non-residues → no points
• Total: 8 points + $\mathcal{O}$ = group order 9

Why it matters: enumerating every point is how you obtain the group order $|E|$ — and it's the largest prime factor of $|E|$ that governs how hard the discrete-log problem on the curve is.

Go deeper:

• Quadratic residue — Wikipedia — which right-hand-side values have a square root mod $p$ (the Legendre symbol).
• Elliptic curve — Wikipedia — points over finite fields and how they are counted.