Context: paper on pairing based cryptography, question 1, question 2.

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.)

  • 2
    $\begingroup$ 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. $\endgroup$
    – Ievgeni
    Jul 21 at 15:57

1 Answer 1


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.

  • $\begingroup$ But how would I determine the embedding degree for $E:y^2=x^3+x$ if $m$ is not odd? $\endgroup$ Jul 24 at 7:30
  • 1
    $\begingroup$ It turns out that I had failed to spot an identity which I have now added to the end of the answer. $\endgroup$
    – Daniel S
    Jul 24 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.