GF(p) 上 n 次不可约多项式的个数

hbghlyj

云 0.4. 我们来计算$p$元有限域上$n$次不可约多项式的个数$P(d)$, 有
\[P(d) = \frac{\phi(p^n - 1)}{n}.\]
证明. 不可约的$n$次多项式都是$x^{p^n-1}-1$的因子.

这个推理的缺陷是什么？

hbghlyj

hbghlyj 发表于 2024-10-13 19:27
这个推理的缺陷是什么？

我在有关本原多项式的页面上看到了相同的公式：

There are
\[a_q(n)=\frac{\phi(q^n-1)}n\]
primitive polynomials over $\hbox{GF}(q)$

所以这个公式只计算本原多项式数！

本原多项式是不可约多项式，但并非所有不可约多项式都是本原多项式！

Maurice R. Kibler, Galois Fields and Galois Rings Made Easy
§2.3.5.12 Number of primitive polynomials
Proposition 2.15 The number of primitive polynomials of the Galois field $\hbox{GF}(p^m)$, i.e. the number of primitive polynomials of degree $m$ over $\mathbb F_p$, is $\frac1m(φ(p^m−1))$, where φ is the Euler function (see Appendix for the definition of φ).

people.eecs.berkeley.edu/~ananth/229BSpr05/ffnotes05.pdf
Corollary 1 The number of primitive polynomials in $\hbox{GF}(2)[x]$ of degree $m$ is exactly $\frac{\phi\left(2^m-1\right)}{m}$.
Proof: Every primitive polynomials in $\hbox{GF}(2)[x]$ of degree $m$ shows up exactly once as a factor of $x\left(x^{2^m-1}-1\right)$. There are exactly $\phi\left(2^m-1\right)$ primitive elements in a field of size $2^m$ and the nonzero elements of $F$ are all roots of $x^{2^m-1}-1$, so their minimal polynomials are factors of $x^{2^m-1}-1$. The minimal polynomials of the primitive elements must be primitive and of degree $m$, and each of the

hbghlyj

hbghlyj 发表于 2024-10-19 08:40
并非所有不可约多项式都是本原多项式

例如，分圆多项式 $x^4+x^3+x^2+x+1$ 是不可约的但不是本原的。
从另一个角度来看：可以证明对于 $\hbox{GF}(2)$ 上的任何不可约多项式 $p(x)$，$\hbox{GF}(2)[x]/⟨p(x)⟩$ 是一个域，而且，说多项式 $p(x)$ 是本原的等价于说 $x$ 是 $\hbox{GF}(2)[x]/⟨p(x)⟩$ 乘法群的生成元。

所以在上面的例子中，$x^4+x^3+x^2+x+1$ 是不可约的，所以 $\hbox{GF}(2)[x]/⟨x^4+x^3+x^2+x+1⟩$ 是一个域，但由于 $x^4+x^3+x^2+x+1$ 不是本原的，$x$ 不是 $\hbox{GF}(2)[x]/⟨x^4+x^3+x^2+x+1⟩$ 乘法群的生成元，但由于有限域的乘法群总是循环的，所以一定有生成元，事实上我们可以找到生成元 $x+1$、$x^2+1$、$x^2+x$、$x^2+x+1$ 等等。

hbghlyj

例如，Matlab 无法使用上述多项式 $x^4 + x^3 + x^2 + x + 1$ “创建”域GF(2^4)的元素：

>> a=gf(15, 4, 'x^4 + x^3 + x^2 + x + 1')
Error using gf (line 96)
PRIM_POLY must be a primitive polynomial.


Matlab 无法完成此操作，但数学上可以做到。

hbghlyj

A001037

• Number of degree-n irreducible polynomials over GF(2);
• number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n;
• number of binary Lyndon words of length n.

\[
a(n) = \frac{1}{n} \sum_{d \mid n} \mu\left(\frac{n}{d}\right) 2^d
\]