Points of an elliptic curve

How it works

For a small prime $p$ all points of $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ can be listed: for every $x$, compute $f(x) = x^3 + ax + b$ and check with Euler’s criterion whether it is a square modulo $p$. A non-zero square gives two points $(x, \pm y)$, a zero gives one point $(x, 0)$, and a non-square none. With the point at infinity, this counts $\#E(\mathbb{F}_p)$.

Hasse’s theorem says that the count is close to $p + 1$: $|\#E - (p + 1)| \le 2\sqrt{p}$. The difference $t = p + 1 - \#E$ is the trace of Frobenius. For cryptographic sizes points are not listed one by one; the count is computed with Schoof’s algorithm and its improvements.

By Lagrange’s theorem the order of every point divides $\#E$. The group is always isomorphic to $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$ with $n_1 \mid n_2$, and it is cyclic when some point has order $\#E$. Cryptography wants a point of large prime order; curves with $\#E = p$ (anomalous) or $t \equiv 0 \pmod p$ (supersingular) must be avoided for discrete logarithm based schemes, because special attacks apply.