Before computing on an elliptic curve $y^2 \equiv x^3 + ax + b \pmod p$, which checks tell you whether the curve is usable, whether a point lies on it, and whether a claimed number of points is plausible? Apply them to: $y^2 = x^3 + 3x + 6$ over $\mathbb{Z}_{21}$; $y^2 = x^3 + 3x + 10$ over $\mathbb{Z}_{13}$; $y^2 = x^3 + 4x + 2$ over $\mathbb{Z}_{29}$.

The modulus must be prime and $4a^3 + 27b^2 \not\equiv 0 \pmod p$. A point lies on the curve if both sides agree mod $p$. Hasse bounds the point count by $p + 1 \pm 2\sqrt{p}$. Only the curve over $\mathbb{Z}_{29}$ is valid.

1. Valid curve:

• The modulus $p$ must be a prime (here we work over prime fields).
• Non-singularity: $4a^3 + 27b^2 \not\equiv 0 \pmod p$; otherwise the curve has a cusp or self-intersection and the group law breaks.

Applied:

• over $\mathbb{Z}_{21}$: invalid, since 21 is not prime.
• over $\mathbb{Z}_{13}$: $4 \cdot 27 + 27 \cdot 100 = 2808 = 13 \cdot 216 \equiv 0$, so singular, invalid.
• over $\mathbb{Z}_{29}$: $4 \cdot 64 + 27 \cdot 4 = 364 \equiv 16 \not\equiv 0$, so valid.

2. Point on the curve: reduce the coordinates mod $p$ first, then compare $y^2$ with $x^3 + ax + b$. Example: $T(-6; 53)$ on $y^2 = x^3 + 2x + 11$ over $\mathbb{Z}_{19}$ becomes $(13; 15)$. Then $15^2 \equiv 16$ but $13^3 + 2 \cdot 13 + 11 \equiv 11$, so $T$ is not on the curve.

3. Plausible point count (Hasse): $p + 1 - 2\sqrt{p} \le |E| \le p + 1 + 2\sqrt{p}$. For $p = 19$: $20 \pm 8.7$, so $12 \le |E| \le 28$. A claim of 21 points is possible; a claim of 32 points is impossible.