本原多項式定義

一個 m 階的不可約多項式 $f(x)$，如果 $f(x)$ 整除 $x^n+1$ 的最小正整數(shù) n 滿足 $n=2^m?1$ ，則該多項式是本原的。

參考定義（百度上的定義）：
設(shè) $f(x)=a_0+a_{1}x+a_2{x}^2+?+a_n{x}^n$是唯一分解整環(huán)$D$上的多項式，如果 $\gcd (a_0+a_1+?+a_n)=1$ ，則稱 $f(x)$為$D$上的一個本原多項式 。（符號 $\gcd ()$表示最大公約數(shù)）
本原多項式滿足以下條件：

1. $f(x)$是既約的，即不能再分解因式；
2. $f(x)$可整除 $x^m+1$，這里的 $m=2^n?1$ ；
3. $f(x)$不能整除 $x^q+1$，這里$q<m$ 。

那么什么是上面說的整除呢？

先插一個百度上查到的一個本原多項式表的圖（應(yīng)該是 GF（2）上的本原多項式）

以第一個階為 2 的本原多項式為例 $f(x)=x^2+x+1$ ：

我們可以得到
$$\begin{gathered} x^0=1 \\ {x}^1=x \\ {x}^2=x+1 \\ {x}^3=x^0=1 \end{gathered}$$
所以 $n=3$ 時 $f(x)$ 整除 $x^n+1(x^3+1=1+1=0)$
且 $3=2^2?1$ 并不存在任意正整數(shù) $q<3$ 使得 $f(x)$ 整除 $x^n+1$ 。

以上為我個人理解