How can I calculate a Point $P \in E(a, b, \mathbb{F}_p)$ of order $3$

Question

Let $$E(a, b, \mathbb{F}_{p} ) = y^2 = f(x) = x^3 + ax + b$$ Find for $E(-4, 0, \mathbb{F}_{541} )$ all points of order $2$ and one point of order $3$.

In this case the points of order $2$ are easy to calculate, because these are the roots of polynom $f(x)$ (where $y = 0$). $$x^3 - 4x = (x - 2)(x + 2)$$
Thus $2P :=\{ (0,\,0), (2,\,0), (-2,\,0)\}$

Now, how can I calculate a Point $P : 3P = \mathcal{O}$? I only deduce that: $$3P = P + P + P \implies P + P = -P \implies 2P = -P$$ How can I continue here to find $P$?

Answer 1

By eye: input in values for $\;x\;$ and find out, for example with the help of Legendre's symbol and quadratic reciprocity, whether you have a solution. To actually find the solution may be way messier, but at least you'll already know whether there exists one or not. For example (note that $\;541=1\pmod4\;$):

$$x=3\implies 3^3-4\cdot3=15\;,\;\;\left(\frac{15}{541}\right)=\left(\frac3{541}\right)\left(\frac5{541}\right)=\left(\frac{541}3\right)\left(\frac{541}5\right)=$$

$$=\left(\frac13\right)\left(\frac15\right)=1\cdot1=1\implies \text{there exists}\;\;\sqrt{15}\pmod{541}$$

After some work (you can use the web for this), one finds $\;\sqrt{15}=\pm189\pmod{541}\;$ ,so we have the solutions $\;(3,189),\,(3,-189)=(3,352)\;$

You can do the above for several values of $\;x\pmod{541}\;$ , but it is going to take a while...and then you have to check what their order in the group is carrying on the operation... You can use the web to make calculations easier, or you can even build a computer program to do the calculations, but it is going to be weary. Why do you think there's a point of order three, btw?

Answer 2

In general one can use division polynomials to compute the coordinates of the $n$-torsion points of an elliptic curve. In this example, the third division polynomial is $$ \psi_3 = 3x^4 + 517x^2 + 525 = 3(x^2 + 148)(x^2 + 385) $$ and its roots give the $x$-coordinates of the $3$-torsion points. Since $x^2 + 148$ and $x^2 + 385$ have no roots in $F = \mathbb{F}_{541}$, then there are no nontrivial $3$-torsion points defined over $F$. Let $\alpha$ be a root of $x^2 + 148$ and let $K = F(\alpha) \cong \mathbb{F}_{541^2}$. Then $\psi_3$ factors over $K$ as $$ \psi_3 = 3(x - \alpha)(x + \alpha)(x - 178 \alpha)(x + 178 \alpha) $$ so the $x$-coordinates of the $3$-torsion points are $\pm \alpha, \pm 178 \alpha$. Unfortunately the $y$-coordinates of these points are not defined over $K$, so letting $\beta = \sqrt{\alpha^3 - 4\alpha}$ and $L = K(\beta) \cong \mathbb{F}_{541^4},$ we find that the nontrivial $3$-torsion points of $E$ are $$ (\alpha, \pm \beta), \ (-\alpha, \pm 52 \beta), \ (178 \alpha, \pm 86 \beta), \ (-178\alpha, \pm 144\beta) \, . $$

Another more elementary approach would be to use your equation $2P = -P$. Writing $P = (x,y)$, then $-P = (x,-y)$. The coordinates of $2P$ can also be expressed in terms of $x$ and $y$ (see here), and equating these with the coordinates of $-P$ will give you a system of equations to solve. (I think the equation you get for the $x$-coordinate will be $\psi_3 = 0$, so the two approaches should be equivalent.)