注意：在粘贴过程中，以下文字会出现问题，原文请到http://download.csdn.net/source/486482下载
伪随机序列是指具有类似f随机噪声序列的统计特性，
又便于进行重复产生和处王If!的数槲J 列。它具有随机噪声的
优点又避免了随机噪声的缺 t ，在数字通信误码牢测量、时
廷测量、通信加密、扩频通信等领域中具有广泛的用途。在
伪随机序列的生成过程中，本原多项式的寻找是产生伪随机
序列的关键，而本原多项j的寻找和生成是一个复杂的过
程，需露大量的计算，允其是当似数较 高时，更是难以得到
这大大限制了伪随机序列的 应用。本文通过对本原多项式的
定义和特性进行研究，给出寻找n次全部本原多项武
的计算机通用算法，井通过验证证明了算法的正确性。该算
法的提出为伪随机序列中本原多项式的寻找提供了有效的手
段，具有霞要的实际应用价值。
2．2寻找GF(2)匕全部本原多项式的通用算法
GF(2)上n次多项式的通式为
Rx)=X'I+ ．I x ‘ + ：x +···+a1 x+ l (4)
其中系数an．．，?，a。是二元域上的元素(0，1)，所以GF(2)上
共有2 个n次多项式。
要判断这些n次多项式是否为本原多项式，首先根据定
义，本原多项式一定是既约多项式，0和1不可能是fx)的根
(因为既约多项式既不能整除x，也不能整除x+1)，所以
1，且fIx)的项数一定为奇数，即 +?+a．=1。其次，
根据代数理论，一个本原多项式的互反多项式也一定是本原
多项式。这样，2”个多项式中，需要判断是否为本原多项式
的个数实际上只有2”。个了。
另外，一个n次既约多项式是否能形成GF(2“)，从而判
断它是否为本原多项式。n次二元多项式的扩域(n位)，其中
0(n位)，1(oo?1)， 。(oo?0)， ，?， ，一定在扩域
中，需要判断的是 ”。， ?， ：”一，是否也在扩域中，
从而形成全部扩域GF(2 )，如果 ” ， ? ， ”之在扩域中，
则该n次既约多项式是本原多项式；否则，该n次既约多项式
不是本原多项式。
由此给出GF(2)上全部本原多项式的通用算法：
(1)给定二厄多项式
“ 产 、十 I_l 。+ l-1 x +·--ai x+a【l ( l=1) (5)
设 是fx)扩域中的一个元素，且f( )=0，则有：
( 。 = al-l( 。+．．．+aI( +1
(2)从 ”。开始，计算 的的连续幂。在计算过程中，
当遇剑 的幂次等于n时，将(5)式代入，一直计算到 !
(形成GF(2”))，再计算 ! ‘。若 一‘=1，则证明fIx)能整
除XlYI+1(m=2”。。)，而不能整除xLl+1(m<q)，判定为本原多项
式。在计算 的连续幂过程中，若 1(q<2” )，则证明fix)
能整除 +1，但q<2”一，判定为非本原多项式，停止计算。
在计算机实现时，由于n个分量的有序序列(an．．，?，a。，a0)
与 的任一连续幂有着一‘一对应的关系，可用有序序列( ，
， a。， )来表示口的任一连续幂。同时，若 用(aq．。，
， aq。，aq。)来表示， 用(an ，?，a 。，a 。)表示，则 可
以用(aq ，?，aq。，a 。)左移一位来表示，若移位前最高位flq 。=
1，表示出现了 ”，则 ‘的有序序列表示为(aq + ．，
， a“．+a ．，a ，+a¨¨)，其中加法为模2相加，这样可以方便
地得到 的连续幂。同时，由于在GF(2)上，有序序列(an．．，
a )总共只能表示 n个不同的数，若用十进制数 2n—I+
a．2+ao来表示该有序序列，则该数必在0到2 一1之间。因而
若fix)的根 能够形成全部扩域GF(2 )，则 的连续幂应能
够形成从0到2”一1之间的所有数。可将所有 的连续幂的十进
制表示求和，若其和为
SUM=I+2+3+?+(2 ．1)=2：n‘。+2 n’。
则认为该本原多项式的根形成了全部扩域。综上所述，在计
算过程中，若 =1(q<2 。)=1，则判定为非本原多项式。否
则，若 都不为I(q<2“ )，且 为1，同时 的所有连续
幂的十进制表示之和为2 一+2“一，则判定fIx)为本原多项式。
联系客服
