# Follow-up II: Number of points on an elliptic curve

Let $$E: y^2 = x^3+x$$ be an elliptic curve over $$\mathbb{F}_{q}$$ where $$q=3^m$$ for some $$m\geq 1$$. Then I know that $$\# E(\mathbb{F}_{q}) = \left\{ \begin{array}{ll}q+1 - 2\sqrt{q} & m\equiv 0 \mod 4\\ q+1 &m\equiv \pm1 \mod 4\\ q+1 + 2\sqrt{q} & m\equiv 2\mod 4 \end{array} \right.$$

From this how can I determine the embedding degree of the curve? I need to find $$k\in \{1,2,3,4,6\}$$ such that for a prime divisor $$n$$ of $$\#E(\mathbb{F}_q)$$ I have that $$n\mid q^k-1$$ but $$n\nmid q^l-1$$ for all $$1\leq l< k$$.

It obviously cannot be $$k=1$$, $$k=2$$, nor $$k=3$$. It cannot be $$k=4$$ either because $$n\nmid q^2 -1$$ and $$n\nmid q^2+1$$. But why is it then that $$k=6$$? (Other than arguing via elimination.)

• Why do you exclude $k=1$? If m is odd, then q+1 and q-1 are both even, and then have $2$ as a common prime factor. Jul 21 at 15:57

Actually, this curve has embedding degree 2 in the case $$m\equiv\pm 1\pmod 4$$ and 1 in the case $$m\equiv 0,2\pmod 4$$. For an embedding degree 6 curve you need to return to the curve of your previous question and consider the cases $$m\equiv\pm1,\pm5\pmod{12}$$ where the point counts are $$q+1\pm\sqrt{3q}$$.
To understand these constructions the next step is to consider the factorisation of cyclotomic expressions. As polynomials over the integers we have the following identities $$x-1=\phi_1(x)$$ $$x^2-1=\phi_1(x)\phi_2(x)$$ $$x^3-1=\phi_1(x)\phi_3(x)$$ $$x^4-1=\phi_1(x)\phi_2(x)\phi_4(x)$$ $$x^6-1=\phi_1(x)\phi_2(x)\phi_3(x)\phi_6(x)$$ where $$\phi_1(x)=x-1$$ $$\phi_2(x)=x+1$$ $$\phi_3(x)=x^2+x+1$$ $$\phi_4(x)=x^2+1$$ $$\phi_6(x)=x^2-x+1.$$ These mean that if we want a prime $$p$$ such that $$p|q^k-1$$ but $$p\not| q^\ell-1$$ for smaller $$\ell$$, then we must have $$p|\phi_k(q)$$.
Now we also seem to be getting expression where $$\sqrt q$$ crops up, so it is worth checking out how these expression factor as polynomials in $$\sqrt q$$. The following may appear to be pulled out of a hat if you've worked with extension fields and splitting fields a great deal, but are easily verified from the high school formulae $$(a+b)^2=a^2+2ab+b^2$$ and $$(a+b)(a-b)=a^2-b^2$$: $$\phi_3(q)=q^2+q+1=(q+1-\sqrt q)(q+1+\sqrt q)$$ $$\phi_4(q)=q^2+1=(q+1-\sqrt{2q})(q+1+\sqrt{2q})$$ $$\phi_6(q)=q^2-q+1=(q+1-\sqrt{3q})(q+1+\sqrt{3q}).$$
Now we notice that for the curve $$y^2=x^3-x+1$$ any prime that divide $$\#E(\mathbb F_{3^m})$$ in the case $$m\equiv\pm1,\pm5\pmod{12}$$ divides one of the brackets on the right hand side of the factorisation of $$\phi_6(q)$$ and hence divides $$\phi_6(q)$$ and hence divides $$q^6-1$$. This tells us that the embedding degree is at most 6. Now, we might worry that the prime also divides one of $$q^5-1$$, $$q^4-1$$,... $$q-1$$. However if $$p|(q^5-1)$$ and $$p|(q^6-1)$$ then $$p|(q^6-q^5)$$ and we quickly deduce that $$p|q-1$$. In the other case we see that $$p$$ would divide one of our cyclotomic polynomials and quickly conclude that either $$p|q$$ or $$p=2$$.
For the point counts in this question, we note that for $$m\equiv 1\pmod2$$ we have $$q+1=\phi_2(q)$$ so that the embedding degree is 2 unless $$p=2$$. For $$m\equiv 0\pmod 2$$ we note that $$(q+1-2\sqrt q)(q+1+2\sqrt q)=q^2-2q+1=(q-1)^2$$ so that if $$p|(q+1\pm2\sqrt q)$$ then $$p|q-1$$ and so the embedding degree is 1.
• But how would I determine the embedding degree for $E:y^2=x^3+x$ if $m$ is not odd? Jul 24 at 7:30