Primitive Polynomial & Cyclotomic Coset

前置知识：有限域、不可约多项式、分圆多项式

最近在学习LDPC、MDPC码的时候，涉及到了很多多项式的知识，对有限域上的多项式又加深了一些理解，所以在这里记录一下，可能会比较乱，相当于是一个随笔。

Primitive Polynomial

我们首先看wiki百科对于本原多项式的定义：

In different branches of mathematics, primitive polynomial may refer to:

• Primitive polynomial (field theory), a minimal polynomial of an extension of finite fields
• Primitive polynomial (ring theory), a polynomial with coprime coefficients

在本篇博客中，我们主要关注于有限域上的本原多项式，因为有限域上的本原多项式有很多有趣的性质：

• 首先从定义中可知，有限域上的本原多项式一定是不可约多项式（irreducible）。
  Proof：根据定义可知，本原多项式是满足本原根的最小多项式。
• 有限域 $\operatorname{GF}(p)$ 上的 $m$ 次不可约多项式 $F(x)$（其中 $p$ 是质数），如果满足 $F(x)$ 整除 $x^n - 1$ 最小$n$ 等于 $p^m - 1$，则多项式 $F(x)$为本原多项式。
  Proof：最小$n$ 等于 $p^m - 1$意味着 $F(x)$ 存在一个根仅在${p^m-1}$次的时候才等于1，即为本原单位根。
• $m$次的本原多项式在$\operatorname{GF}(p^m)$有$m$个不同的（共轭）根，均是本原单位根，且这些根构成了一个分圆陪集（cyclic coset）。
  Proof：考虑$s$与$p^m-1$互素，那么$sp^k$必与$p^m-1$互素，而且分圆陪集中的元素恰有$m$个$\{s,sp,sp^2,\dots,sp^{m-1}\}$。
• 在$\operatorname{GF}(p)$上，恰好有$\varphi\left(p^m-1\right)$本原元和$\varphi\left(p^m-1\right)/m$本原多项式，次数均为$m$。
  Proof：见上一条证明

如何理解本原多项式引导出的扩域呢？我们可以类比$\mathbb{R}$到$\mathbb{C}$的代数扩展：取$f (x) = x^2 + 1 \in \mathbb{R}(x)$，并将虚数定义为$f (i) = 0$。之后我们可以在$\mathbb{R}$中附加$i$，从而得到一个$\mathbb{R}$上的二维空间$\mathbb{C}$。
我们现在回过头来看$\mathbb{F}_{2^4}=\mathbb{F}_{16}$，选取本原多项式$f(\alpha)=\alpha^4 + \alpha + 1$，我们有$\alpha^4 = \alpha + 1$，从而在$\mathbb{F}_2$中附加$\alpha$，由于$1,\alpha,\alpha^2,\alpha^3$互相之间不存在线性关系，因此我们可以得到一个$\mathbb{F}_2$上的四维空间$\mathbb{F}_{16}$，任何高于四次的多项式都可以通过$\alpha^4 = \alpha + 1$进行简化。（任何高于四维的元素都是线性相关的）

Cyclotomic Coset

接下来我们给出一些更有趣的概念：
Lemma：$(x+y)^{p^m} = x^{p^m} + y^{p^m} \mod p$

Proof：

$$\begin{aligned} & (x+y)^p=x^p+\ldots+\binom{p}{i} x^{p-i} y^i+\ldots+y^p \\ & \binom{p}{i}=\frac{p(p-1) \ldots(p-i+1)}{i(i-1) \ldots} \equiv 0 \bmod p \quad \text { for } i \neq 0, n \\ &(x+y)^{p^m} \equiv\left[(x+y)^{p^{m-1}}\right]^p \equiv\left[(x)^{p^{m-1}}+(y)^{p^{m-1}}\right]^p \equiv x^{p^m}+y^{p^m} \bmod p \end{aligned}$$

Theorem： 如果$\beta \in \mathbb{F}_{p^m}$，那么 $\beta$ 和 $\beta^p$有相同的最小多项式。
Proof： $f\left(\beta^p\right)=\sum f_i \beta^{p i}=\left(\sum f_i \beta^i\right)^p=(f(\beta))^p=0$

我们进一步来看一些有趣的性质：我们令本原多项式为$f(\alpha)=\alpha^4 + \alpha + 1$，可以看到$\alpha, \alpha^2, \alpha^4, \alpha^8$有相同的最小多项式，并且该多项式恰有四个根。

$$\begin{aligned} m(x)&=(x-\alpha)\left(x-\alpha^2\right)\left(x-\alpha^4\right)\left(x-\alpha^8\right)\\ &= x^4 - (\alpha^8 + \alpha^4 + \alpha^2 + \alpha)x^3 + (\alpha^{12} + \alpha^{10} + \alpha^{9} + \alpha^6 + \alpha^5 + \alpha^3)x^2 - (\alpha^{14} + \alpha^{13} + \alpha^{11} + \alpha^7)x + \alpha^{15} \end{aligned}$$

可以发现每一项的系数$b$都满足$b^2=b$，因此$b$一定位于$\mathbb{F}_2中$。

$$\begin{aligned} (\alpha^8 + \alpha^4 + \alpha^2 + \alpha)^2 &= \alpha^{16} + \alpha^8 + \alpha^4 + \alpha^2 = \alpha + \alpha^8 + \alpha^4 + \alpha^2\\ (\alpha^{12} + \alpha^{10} + \alpha^{9} + \alpha^6 + \alpha^5 + \alpha^3)^2 &= \alpha^{24} + \alpha^{20} + \alpha^{18} + \alpha^{12} + \alpha^{10} + \alpha^6 = \alpha^{9} + \alpha^{5} + \alpha^{3} + \alpha^{12} + \alpha^{10} + \alpha^3\\ (\alpha^{14} + \alpha^{13} + \alpha^{11} + \alpha^7)^2 &= \alpha^{28} + \alpha^{26} + \alpha^{22} + \alpha^{14} = \alpha^{13} + \alpha^{11} + \alpha^{7} + \alpha^{14}\\ \end{aligned}$$

其实，很容易证明，任意一个分圆陪集构造出来的系数都位于$\mathbb{F}_2$中。

Definition：分圆陪集(Cyclotomic Coset)是一个集合，模$p$的分圆陪集为$\{s,sp,sp^2,\dots,sp^{m-1}\}$。

$$\begin{aligned} &\text { Example: } \mathrm{p}=2, \mathrm{m}=4\\ &\begin{array}{ll} C_0=\{0\} & m_0=x+1 \\ C_1=\{1,2,4,8\} & m_1=x^4+x+1=m_2=m_4=m_8 \\ C_3=\{3,6,9,12\} & m_3=x^4+x^3+x^2+x+1=m_6=m_9=m_{12} \\ C_5=\{5,10\} & m_5=x^2+x+1=m_{10} \\ C_7=\{7,11,13,14\} & m_7=x^4+x^3+1=m_{11}=m_{13}=m_{14} \end{array} \end{aligned}$$

由上面我们又想到了一个等式：

$$m_1(x) m_3(x) m_5(x) m_7(x) = x^{16} - 1$$

$m_1(x),m_3(x),m_5(x),m_7(x)$并非都是本原多项式，其中只有$m_1(x), m_7(x)$是本原多项式（1和7与15互素）。注意这些多项式与分圆多项式之间的区别：分圆多项式应该是$m_1(x) m_7(x)$。这是不是又是一种快速求分圆多项式的方法呢？（尝试一下还真是，数学真是奇妙啊!）
整理一下这个方法：首先我们要找到一个本原多项式，然后利用这个本原根生成不同分圆陪集的最小多项式，利用其中与$p^m-1$互素的多项式相乘，就可以得到分圆多项式。

仙人指路

之所以叫仙人指路是因为我是看到了这一个例子才理解了Cyclotomic Coset这个概念，放在这里仅供参考。

Over GF(3) the polynomial $x^2+1$ is irreducible but not primitive because it divides $x^4-1$ : its roots generate a cyclic group of order 4 , while the multiplicative group of $\operatorname{GF}\left(3^2\right)$ is a cyclic group of order 8 . The polynomial $x^2+2 x+2$, on the other hand, is primitive. Denote one of its roots by $\alpha$. Then, because the natural numbers less than and relatively prime to $3^2-1=8$ are $1,3,5$, and 7 , the four primitive roots in $\mathrm{GF}\left(3^2\right)$ are $\alpha, \alpha^3=2 \alpha+1, \alpha^5=2 \alpha$, and $\alpha^7=\alpha+2$. The primitive roots $\alpha$ and $\alpha^3$ are algebraically conjugate. Indeed $x^2+2 x+2=(x-\alpha)(x-(2 \alpha+1))$. The remaining primitive roots $\alpha^5$ and $\alpha^7=\left(\alpha^5\right)^3$ are also algebraically conjugate and produce the second primitive polynomial: $x^2+x+2=(x-2 \alpha)(x-(\alpha+2))$.

For degree $3, \operatorname{GF}\left(3^3\right)$ has $\varphi\left(3^3-1\right)=\varphi(26)=12$ primitive elements. As each primitive polynomial of degree 3 has three roots, all necessarily primitive, there are $12 / 3=4$ primitive polynomials of degree 3 . One primitive polynomial is $x^3+2 x+1$. Denoting one of its roots by $\gamma$, the algebraically conjugate elements are $\gamma^3$ and $\gamma^9$. The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements $\gamma^r$ with $r$ relatively prime to 26 :

$$\begin{aligned} x^3+2 x+1 & =(x-\gamma)\left(x-\gamma^3\right)\left(x-\gamma^9\right) \\ x^3+2 x^2+x+1 & =\left(x-\gamma^5\right)\left(x-\gamma^{5 \cdot 3}\right)\left(x-\gamma^{5 \cdot 9}\right)=\left(x-\gamma^5\right)\left(x-\gamma^{15}\right)\left(x-\gamma^{19}\right) \\ x^3+x^2+2 x+1 & =\left(x-\gamma^7\right)\left(x-\gamma^{7 \cdot 3}\right)\left(x-\gamma^{7 \cdot 9}\right)=\left(x-\gamma^7\right)\left(x-\gamma^{21}\right)\left(x-\gamma^{11}\right) \\ x^3+2 x^2+1 & =\left(x-\gamma^{17}\right)\left(x-\gamma^{17 \cdot 3}\right)\left(x-\gamma^{17 \cdot 9}\right)=\left(x-\gamma^{17}\right)\left(x-\gamma^{25}\right)\left(x-\gamma^{23}\right) \end{aligned}$$

References

[1] https://en.wikipedia.org/wiki/Primitive_polynomial
[2] https://wuli.wiki/online/FldExp.html
[3] Ouzan S, Be’ery Y. Moderate-density parity-check codes[J]. arXiv preprint arXiv:0911.3262, 2009.
[4] https://user.eng.umd.edu/~abarg/626/