本原多项式_本原多项式举例_高斯引理 本原多项式

本原多项式本原多项式

(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

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-37681-1.html