Elliptic Curve Crypto

It is well-known that if $p \nmid m,$ the set of $m$ -torsion points over $\overline{{\mathbb F}_p},$ the algebraic closure of the finite field ${\mathbb F}_p,$ is isomorphic to ${\mathbb Z}/m \times {\mathbb Z}/m.$ So there are nine $3$ -torsion points over the algebraic closure, hence $8$ points of order $3.$ This means that the maximum is at most $8$ , and all that remains is to find an elliptic curve with full $3$ -torsion over ${\mathbb F}_p.$ As Mark Hennings points out, $y^2=x^3+1$ will do for $p=31.$

Recall the formulas for point doubling: $s = (3x^{2} + a)(2y^{-1})$ , $x_{new} = s^{2} - 2x$ , $y_{new} = s(x_{new} - x) - y$ .

Since 2P = -P, we know that $x_{new} = x$ and that $y_{new} = -y$ .

We look at the equation for $x_{new}$ and use substitution to get $s^{2} - 3x = 0$ . If we work out what $s^{2}$ is, then we can generate the equation $9x^{4} + 6ax^{2} + a^{2} - 3x(4y^{2}) = 0$ . Since we know $y^{2}$ from our equation for the curve E, we substitute that to get $9x^{4} + 6ax^{2} + a^{2} - 3x(4x^{3} + 4ax + 4b) = 0$ which simplifies to $3x^{4} + 6ax^{2} + 12bx - a^{2} = 0$ .

This implies that there are four x values to satisfy the equation. And for four distinct x-values on the curve, there are two y-values. So then we have at most 8 points of order 3.