原多项式定义了m阶不可约多项式f(x(largef ) x ) f ) x ),当f(x ) largef ) x )满足xn1(largex ) n1xn1的最小正整数n满足n=2m1 ) largen1时
参考定义(百度上的定义) :
当f(x )=a0 a1 x a2 x2 an xn(largef ) x )=a_0a_1xa_2x^2) Cdotsa_NX^nf ) x )=a0a1xa2x2anxn是唯一分解整环D D D上的多项式时
1 gcd (a_0+a_1+cdots+a_n)=1 gcd(a0+a1+⋯+an)=1 ,则称 f ( x ) large f(x) f(x)为 D D D上的一个本原多项式 。(符号 gcd ( ) gcd() gcd()表示最大公约数)本原多项式满足以下条件: f ( x ) large f(x) f(x)是既约的,即不能再分解因式; f ( x ) large f(x) f(x)可整除 x m + 1 large x^m+1 xm+1,这里的 m = 2 n − 1 large m=2^n-1 m=2n−1 ; f ( x ) large f(x) f(x)不能整除 x q + 1 large x^q+1 xq+1,这里 q < m large q<m q<m 。
那么什么是上面说的整除呢?
先插一个百度上查到的一个本原多项式表的图(应该是 GF(2)上的本原多项式)
以第一个阶为 2 的本原多项式为例 f ( x ) = x 2 + x + 1 f(x)=x^2+x+1 f(x)=x2+x+1 :
我们可以得到
x 0 = 1 x 1 = x x 2 = x + 1 x 3 = x 0 = 1 x^0=1\ x^1 = x \ x^2 = x+1 \ x^3 = x^0=1 \ x0=1x1=xx2=x+1x3=x0=1
所以 n = 3 n=3 n=3 时 f ( x ) f(x) f(x) 整除 x n + 1 ( x 3 + 1 = 1 + 1 = 0 ) x^n+1 spacespacespace(x^3+1=1+1=0) xn+1 (x3+1=1+1=0)
且 3 = 2 2 − 1 3 = 2^2-1 3=22−1 并不存在任意正整数 q < 3 q<3 q<3 使得 f ( x ) f(x) f(x) 整除 x n + 1 x^n+1 xn+1 。
以上为我个人理解