後續二：橢圓曲線上的點數
背景：關於基於配對的密碼學的論文，問題 1，問題 2。
讓 $ E: y^2 = x^3+x $ 是一條橢圓曲線 $ \mathbb{F}{q} $ 在哪裡 $ q=3^m $ 對於一些 $ m\geq 1 $ . 然後我知道 $$ # 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. $$
從中如何確定曲線的嵌入程度？我需要找到 $ k\in {1,2,3,4,6} $ 這樣對於一個素數除數 $ n $ 的 $ #E(\mathbb{F}_q) $ 我有這個 $ n\mid q^k-1 $ 但 $ n\nmid q^l-1 $ 對所有人 $ 1\leq l< k $ .
顯然不能 $ k=1 $ , $ k=2 $ , 也不 $ k=3 $ . 它不可能是 $ k=4 $ 要麼是因為 $ n\nmid q^2 -1 $ 和 $ n\nmid q^2+1 $ . 但是為什麼會這樣 $ k=6 $ ? （除了通過排除來爭論。）
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.