概述
一個n次不可約多項式,如果隻能整除1+Z^2^n-1
而不能整除其它1-Z^L(L<2^n-1),則這種不可約多項式就稱為本原多項式。
本原多項式的另外一種定義:系數取自GF(p)上,以GF(p^m)上的本原域元素為根的最小多項式。
因為本原多項式一定以n=p^m-1級元素為根,p^m≡1(modn),所以本原多項式的次數必然是m。
對于一個n次多項式,其本原多項式一般有若幹個。下面将給出的一個算法,是求解在給定任意n值及一個本原多項式的情況下,其餘本原多項式的求解方法。該算法的意義在于提供了同一n值情況下若幹個可選的本原多項式,這樣就允許在構造應用系統時有不同的選擇方案。
已知一個n級本原多項式,求解其餘的本原多項式按以下步驟進行。
(1)首先确定n級本原多項式的個數λ(n),λ(n)即是n級本原多項式的個數。
(2)求出小于2n-1且與2n-1互素的所有正整數,構成一個集合〔Si〕,并重新排序,使〔Si〕中元素從小到大排列。
(3)排除〔Si〕中不适合的數
排除〔Si〕中形如2j(j為正整數)
排除〔Si〕中所有同宗的數。即從〔Si〕中從後到前搜索,每取一個數即做2K×Si,直到大于2n-1,然後減去2n-1,用差值在〔Si〕中向前搜索,如果有相同的數則将Si排除,否則保留。再取Si-1按同樣過程做一遍,直到S0。
排除〔Si〕中有倍數關系的數。即從〔Si〕中從後到前搜索,每取一數即向前查詢一遍,最後〔Si〕中剩下的數即為本原抽樣數,其個數一定為λ(n)-1。
(4)根據已知的一個n級本原多項式,為其設置初始狀态000…01(n個),求出其M序列{Ai}(長度為2n-1)。
(5)依次從Si中取出本原抽樣數,每取出一個抽樣數Si,即可求出一個本原多項式:以Si對{Ai}進行抽樣,就可産生長度為2n-1的另一M序列{Si},在{Si}中找到形如000…01(n位)的序列段{Mi},并提取包括{Mi}為前n項的2n長度的序列:
Am+0,Am+1,…,Am+n-1,
0 0 … 1
Am+n,Am+n+1,…Am+2n-1
X X … X
欲确定的Ci可用下列方程組确定;
C1=Am+n
C2=Am+n+1+C1Am+n
C3=Am+n+2+C1Am+n+1+C2Am+n
常用本原多項式
下表為常用本原多項式:
Matlab中調用本原多項式的指令:
primpoly(m);
primpoly(m,'all');
primpoly(m,'all','nodisplay');
注意返回值是按照十進制表示的。
含義
在不同的分支數學,本原多項式有不同的含義:
域論中,一個本原多項式是有限域CF(pm)有限擴張的本原元的最小多項式(域論)。
在代數(特别是環理論),如果一個整系數多項式的所有系數是互數的,則稱它是一個本原多項式,本原多項式對判定不可約多項式有很大的幫助,高次多項式的不可約多項式判定一直是個未完全解決的問題。
有限域的不可約多項式都是本原多項式,這點對通訊編碼和密碼學有重要作用,每個有理系數多項式都能寫成一個有理數與一個本原多項式的乘積。高斯引理(環的)兩個本原多項式的乘積r仍是本原多項式。