0. 前言

在密码学、纠错码理论、数字信号处理等领域，有限域GF(2)上的多项式理论是核心基础之一。其中，不可约多项式与本原多项式的计数问题不仅具有重要的理论意义，更是工程实践中构造有限域结构、设计线性反馈移位寄存器（LFSR）、生成伪随机序列等关键技术的前提。例如，不可约多项式用于定义有限域的运算规则，而本原多项式则是生成最大周期序列（\(m\)序列）的核心要素。

目前，尽管数学理论中已有成熟的计数公式（如基于莫比乌斯函数的不可约多项式计数公式、基于欧拉函数的本原多项式计数公式），但在工程应用中，针对具体次数\(m\)的快速计算及数据查询仍存在需求。尤其当\(m\)较大时，手工计算复杂度极高，现编制计算机程序受制于工程师技能树和需求的性价比。因此，依赖高效的工具或预先整理的数据表格成为必要。

本文聚焦GF(2)域上\(m\)次不可约、自反不可约及本原多项式的数量计算，系统梳理计数公式的数学定义与应用示例，结合 Wolfram 在线工具提供大数计算方法，并通过表格形式呈现\(m \leqslant 72\)的详细数据。

本文旨在为从事通信系统设计、密码算法实现、集成电路开发等领域的工程技术人员提供简明、实用的参考资料，兼顾理论严谨性与工程可操作性，避免复杂数学推导，侧重公式应用、工具使用及数据呈现。

（注：未特别说明的情况下，本文的多项式均特指GF(2)域上的多项式。文中公式较多，可能显示不全，当您读着不顺畅时，不妨刷新试试！）

1. 不可约多项式的数量计算

依定义，不可约多项式（Irreducible Polynomial）指的是：一个次数\( \geqslant 1 \)的、除了1和它本身外不包含其它因式的多项式。GF(2)域\(m\)次多项式可写为：

\[f(x) = a_m x^m + a_{m-1} x^{m-1} + \cdots + a_1 x^1 + a_0\]

因\( f(x) \)是GF(2)域的\(m\)次多项式，故\( a_m=1 \) 。1次多项式共两个：\( x, x+1 \)，都是不可约的。

当\( m>1 \)时，若\( a_0=0 \)，则\( f(x) \)含因式\( x^i,(1 \leqslant i \leqslant m) \)，不符合不可约多项式的定义，故\( a_0=1 \)。可得到GF(2)域\( m(>1) \)次不可约多项式的必要条件是：\( a_m=a_0=1 \)。当GF(2)域多项式的次数\( m(>1) \)确定后，满足不可约必要条件的多项式数量共有\( 2^{m-1} \)个，这是\( m(>1) \)次不可约多项式数量的上界。

GF(2)域\(m\)次不可约多项式的数量可通过下式计算：

\[N(m)=\frac{1}{m} \sum_{d|m} \left [ \mu (d) \cdot 2^{m/d} \right ]\]

其中：

• \( d|m \)表示\(d\)是整除\(m\)的所有正整数（包括1和\(m\)）；
• \( \mu(d) \)是莫比乌斯函数（Möbius function），定义为：
• 若\( d=1 \)，则\( \mu(1)=1 \)；
• 若\(d\)包含次数大于1的素（质）因子，则\( \mu(d)=0 \)。例如\( \mu(12) = \mu(2^2 \times 3)=0 \)；
• 若\(d\)是\(k\)个不同素（质）数的乘积，则\( \mu(d) = (-1)^k \)。例如\( \mu(6) = \mu(2 \times 3) = (-1)^2 = 1 \)，\( \mu(30) = \mu(2 \times 3 \times 5) = (-1)^3 = -1 \)。

\( m = 4 \)，不可约多项式数量的计算示例：

• 找出整除\(m\)所有的正整数：可整除4的因数为\( d=1,2,4 \)；
• 计算每个因数对应的莫比乌斯函数值：\( \mu(1)=1 \)，\( \mu(2) = -1 \)，\( \mu(4) = 0 \)；
• 代入公式计算：

\[\begin{aligned} 
N(4) &= \frac{1}{4} \left [ \mu (1) \cdot 2^4 + \mu (2) \cdot 2^2 + \mu (4) \cdot 2^1 \right ] \\
        &= \frac{1}{4} \left [ 16 - 4 + 0 \right ] \\
        &= 3
\end{aligned}\]

\(m\)的值较大时，通常需编制计算机程序来计算，也有众多的编程算法，本文不讨论。本文基于Wolfram在线工具，在输入框填入（点击链接即可验证结果）：k = DivisorSum[128, 2^(128/#) MoebiusMu[#] &]/128。其中128为待计算的多项式次数\(m\)。计算结果如下图：

可以看到，GF(2)域共有2658455991569831745663498932484833280个128次不可约多项式。

2. 本原多项式的数量计算

依定义，GF(2)域\(m\)次本原多项式（Primitive Polynomial）是不可约多项式，同时它的周期\(e\)满足\(e=2^m-1\)的关系。不可约是本原多项式的必要条件，但不是充分条件，因此，\(m\)次本原多项式的数量小于等于相同次数的不可约多项式数量。

\(m\)次本原多项式的数量可通过下式计算：

\[P(m)=\frac{ \phi (2^m - 1) }{m}\]

其中：

• \( \phi (n) \)是欧拉函数（Euler’s totient function），表示小于等于\(n\)且与\(n\)互素（质）的正整数个数。
• \(n\)是正整数。\( \phi (1) = 1 \)。1不是素（质）数，但与所有大于0的整数互素（质）。
• 当\(m\)是素（质）数时，\( \phi (n) = n - 1 \)。

例如，\( m = 4, n = 2^m - 1 = 15 = 3 \times 5 \)，小于等于15的正整数为1 ~ 15，共15个，其中3,6,9,12,5,10,15与 15 不互素，可得\( \phi (15) = 15-7 = 8 \)，从而可计算出 4 次本原多项式的数量为\( 2 (= 8/4) \)。

\(n (=2^m-1) \)的值较大时，通常需编制计算机程序来计算欧拉函数值，也有众多的编程算法，本文不讨论。本文将基于在线工具完成欧拉函数计算，常见工具通常会限制欧拉函数输入值的范围（例如1000000），而Wolfram无此限制，且可实现多步计算，例如，在Wolfram工具输入框填入（点击链接即可验证结果）：m = 128, n = 2^m - 1, p = EulerPhi[n], k = p/m。其中，m为本原多项式的次数，EulerPhi[n]为Wolfram的欧拉函数，\(k\)为待计算的\(m\)次本原多项式数量。计算结果如下图：

可以看到，GF(2)域共有1327149278901642923121482163604684800个128次本原多项式。

3. 自反不可约多项式的数量计算

GF(2)域上\( m \)次非零（即常数项不为0）的多项式\( f(x) \)可写为：

\[f(x) = a_m x^m + a_{m-1} x^{m-1} + \cdots + a_1 x^1 + a_0\]

存在另一个\( m \)次的非零多项式\( f^*(x) \)，系数与之倒置，即满足\( f^*(x) = x^m f(1/x) \)的关系，称\( f^*(x) \)与\( f(x) \)互为反多项式（Reciprocal Polynomial）。依定义，\( f^*(x) \)可写为：

\[f^*(x) = a_0 x^m + a_{1} x^{m-1} + \cdots + a_{m-1} x^1 + a_m\]

当\( f^*(x) = f(x) \)时，\( f(x) \)称为自反多项式（Self-reciprocal Polynomial）。自反多项式系数满足\( a_i=a_{m-i} \left ( 0 \leqslant i  \leqslant m \right ) \)的关系。当自反多项式不可约时，则称为自反不可约多项式（Self-Reciprocal Irreducible Polynomial，SRIP）。

当\( m=1 \)时，共两个不可约多项式：\( x, x+1 \)，其中\( x+1 \)是自反不可约多项式，同时也是本原多项式。

当\( m=2 \)时，只有一个不可约多项式：\( x^2+x+1 \)，是自反不可约多项式，同时也是本原多项式。

当\( m>2 \)时，不可约多项式、自反不可约多项式、本原多项式有这样一些特性：

• 非零系数项的数目（即汉明重量）为奇数，否则该多项式含因式\( x+1 \)，是可约的；
• 不可约多项式的反多项式也是不可约的，互为反多项式的两个多项式的周期相同；
• 本原多项式的反多项式也是本原的；
• 因自反不可约多项式的项数必须是奇数，故一定存在\( x^{m/2} \)项，即\( a_{m/2} = 1 \)，因此，自反不可约多项式的次数\( m \)一定是偶数，或者说奇次不可约多项式中无自反多项式。从而\( m \)次自反不可约多项式的系数自由项（即可取值0或1）的数目是\( m/2 \)，可得到\( m \)次自反不可约多项式数量的上界值是\( 2^{m/2} \)；
• 本原多项式不能是自反的，即每个本原多项式都有一个与之不相等的、同为本原多项式的反多项式，因此，\( m \)次本原多项式的数量是偶数。同理，\( m \)次不可约非自反多项式的数量也是偶数。

在纠（检）错编码理论中，生成多项式的选择是核心工作，由于互为反多项式的两个多项式具有完全一致的纠（检）错性能，将\( m \)次多项式的全部集合作为备选时，实际工作中只需进行一半的非自反多项式和全部自反多项式的筛选。因此，\( m \)次不可约多项式中自反多项式的数量计算亦有着实际的工程价值。

由前文可知，次数大于1的奇次自反不可约多项式的数量为0。偶数次，即\( m(=2k,k \geqslant 1) \)的自反不可约多项式的数量可通过下式计算\( ^{[1]} \)（见参考文献[1]定理3）：

\[S(m)=\frac{1}{2k} \sum_{\substack{d \mid k \\ d \text{奇}}} \left [ \mu (d) \cdot 2^{k/d} \right ]\]

其中，\( \mu(d) \)是莫比乌斯函数，求和遍历所有整除\( k \)的奇数。

与前文相同，基于Wolfram工具完成计算，以\( m=128 \)为例，在工具的输入框填入：s = DivisorSum[64, 2^(64/#) MoebiusMu[#] &, OddQ[#] &]/(2*64)。其中64表示次数128的一半，\( s \)为计算结果，如下图所示：

可以看到，GF(2)域共有144115188075855872个128次的自反不可约多项式。

4. m = 1 ~ 72次不可约、自反不可约及本原多项式数量列表

当我们需要确定GF(2)域的\(m\)次多项式中，有多少个不可约、自反不可约或本原多项式时，可通过前文的方法，利用Wolfram工具直接计算结果。本文采用此方法计算了\(m \leqslant 72\)的全部结果，列于下表，其中：

• \(m\)列对应数字为多项式次数；
• n_Irre列表示\(m\)次不可约多项式（Irreducible Polynomial）的数量；
• n_Prim列表示\(m\)次本原多项式（Primitive Polynomial）的数量；
• n_SRIP列表示\(m\)次自反不可约多项式（Self-Reciprocal Irreducible Polynomial）的数量；
• 数字红色加粗表示\(m\)的取值满足\( (2^m - 1) \)是素数（即梅森素数，Mersenne prime），则该\(m\)次不可约多项式都是本原多项式。

m	n_Irre	n_Prim	n_SRIP	m	n_Irre	n_Prim	n_SRIP
1	2	1	1	37	3714566310	3697909056	0
2	1	1	1	38	7233615333	4822382628	13797
3	2	2	0	39	14096302710	11928047040	0
4	3	2	1	40	27487764474	11842560000	26214
5	6	6	0	41	53634713550	53630700752	0
6	9	6	1	42	104715342801	57802864896	49929
7	18	18	0	43	204560302842	204064589160	0
8	30	16	2	44	399822314775	200778006528	95325
9	56	48	0	45	781874934568	634404960000	0
10	99	60	3	46	1529755125849	998132265920	182361
11	186	176	0	47	2994414645858	2992477516800	0
12	335	144	5	48	5864061663920	2283043553280	349520
13	630	630	0	49	11488774559616	11398311767808	0
14	1161	756	9	50	22517997465744	13122000000000	671088
15	2182	1800	0	51	44152937520670	37456800827040	0
16	4080	2048	16	52	86607683851185	44980696051200	1290555
17	7710	7710	0	53	169947155749830	169917983040000	0
18	14532	7776	28	54	333599969907456	178118842613760	2485504
19	27594	27594	0	55	655069036708398	598690870272000	0
20	52377	24000	51	56	1286742745883790	598975092817920	4793490
21	99858	84672	0	57	2528336632900554	2167072830474048	0
22	190557	120032	93	58	4969489234738635	3238370502193152	9256395
23	364722	356960	0	59	9770521225481754	9770466930024800	0
24	698870	276480	170	60	19215358392200893	6774451200000000	17895679
25	1342176	1296000	0	61	37800705069076950	37800705069076950	0
26	2580795	1719900	315	62	74382032520643617	49588021611155412	34636833
27	4971008	4202496	0	63	146402730743693304	122428597145960448	0
28	9586395	4741632	585	64	288230376084602880	143890337947975680	67108864
29	18512790	18407808	0	65	567592125344909154	549215642649655800	0
30	35790267	17820000	1091	66	1117984489185516357	594287364124624896	130150493
31	69273666	69273666	0	67	2202596307308603178	2202596295934991760	0
32	134215680	67108864	2048	68	4340410370031955245	2295419955465369600	252645135
33	260300986	211016256	0	69	8555011744328945842	7176808547444088960	0
34	505286415	336849900	3855	70	16865594581186450683	9416895732518400000	490853403
35	981706806	929275200	0	71	33256101992039755026	33255955596453429120	0
36	1908866960	725594112	7280	72	65588423372234846720	23312749520045998080	954437120

5. 梅森素数

一个形如\( M_p = 2^p - 1 \)的整数，当\( M_p \)是素数时，称为梅森素数\( ^{[2] \sim [5]} \)（Mersenne prime）。梅森素数的指数\(p\)也一定是素数，称为梅森指数（Mersenne exponent）。人类发现的前12个梅森指数是：2,3,5,7,13,17,19,31,61,89,107,127。

从前文可知，\(m\)次不可约多项式的数量可通过莫比乌斯函数计算，当\(m\)是素数时，有且只有一个素数因子（即\(m\)自身），依莫比乌斯函数定义可知\( \mu (m) = - 1 \)。代入不可约多项式数量计算公式，有：

\[\begin{aligned}
N(m) &=\frac{1}{m} \sum_{d|m} \left [ \mu (d) \cdot 2^{m/d} \right ] \\
         &=\frac{1}{m} \left [ \mu (1) \cdot 2^{m} + \mu (m) \cdot 2^{1} \right ] \\
         &=\frac{1}{m} (2^m - 2)
\end{aligned}\]

从前文可知，\(m\)次本原多项式的数量可通过欧拉函数计算，当\( (2^m - 1) \)是素数时，依欧拉函数性质可知\( \phi (2^m - 1) = (2^m - 1) - 1 \)。代入本原多项式数量计算公式，有：

\[P(m)=\frac{ \phi (2^m - 1) }{m} = \frac{2^m - 2}{m}\]

综上分析可知，当GF(2)域多项式的次数\(m\)是梅森指数时，这\(m\)次的多项式中，不可约与本原多项式的数量相等，都是：\( (2^m - 2)/m \)。

6. 结语

有限域多项式的计数问题是连接数学理论与工程实践的重要桥梁。本文通过公式解析、工具应用及数据整理，构建了从 “理论公式” 到 “工程参数” 的完整链条，为相关领域的研究与开发提供了高效、可靠的参考。

7. 参考

1. Meyn, Helmut and W. A. Götz. “Self-reciprocal polynomials over finite fields.” (1989).
2. OESI.org, A000668 Mersenne primes[EB/OL].
3. OESI.org, A000043 Mersenne exponents[EB/OL].
4. PrimePages, Mersenne Primes: History, Theorems and Lists[EB/OL].
5. HandWiki.org, Mersenne prime[EB/OL].