论文部分内容阅读
NFSR(非奇异反馈移位寄存器)是一类广泛应用于通信和密码算法中的寄存器。圈结构是用来刻画NFSR状态图的一种常用的表述方式,即该NFSR可以生成多少个圈以及每个圈的圈长是多少;NFSR的圈个数分布问题是指含有确定圈个数的非奇异反馈移位寄存器的计数问题。上个世纪八十年代,国内外学者解决了线性和特定非线性的NFSR圈结构,在圈个数分布问题上,目前仅能确定圈个数为1的NFSR的个数,对于其余NFSR的圈个数分布问题极少有研究结果。同时M序列是一类圈长达到最大的NFSR序列,因其伪随机性质良好和线性复杂度较高而被广泛应用于通信编码中。当前构造M序列的方法主要是“并圈”法和递归法,但是至今都没有较好的构造算法可以快速生成大量的M序列。针对NFSR圈结构和M序列构造研究中存在的问题,本文提出了M序列状态圈的概念,建立了一种以NFSR圈个数为核心的概念关系图,研究了确定圈个数的NFSR个数问题,解决了部分圈个数分布问题,同时给出了一类M序列反馈函数的多项式表示、小项表示等构造方法。取得的主要创新性成果如下:1.圈个数为2的NFSR的个数问题研究将圈个数为2的NFSR的个数问题归结到两个不定方程的正整数解的求解问题,给出了在级数n下,其个数与M序列状态圈中赋值点的关系;基于赋值点分类和等分圈的个数给出了M序列状态圈新的结构属性规律;基于m序列构造了一类圈个数为2的NFSR;给出了NFSR圈个数与反馈函数小项个数的关系,及其与M序列反馈函数小项重量分布的联系。2.圈个数为Z(n)的NFSR的个数问题研究基于纯轮换寄存器因子关联图中的二重边在圈剪接中的作用,给出了圈个数达到Z(n),Z(n)-1,Z(n)-2的NFSR个数下界的计算公式,给出了全体圈个数为Z(n)的NFSR的反馈函数小项表示的形式化描述,提出了圈个数分布规律的合理猜想。同时给出了一个圈个数为Z(n)的NFSR圈长的限制条件以及NFSR综合问题的一个优化算法。3.M序列反馈函数多项式表示构造研究基于由m序列构造M序列反馈函数的结构特性,结合函数变换和函数派生的方式得到一类M序列反馈函数的快速构造方法,并给出了该类M序列反馈函数的多项式表示、计数以及重量性质。4.M序列反馈函数小项表示构造研究给出了纯轮换寄存器因子关联图在素数级情况下的一种确定性结构,据此给出了全部最小权值M序列的理论构造方法,得出了最小权值M序列个数的下界及其对应的反馈函数。本文还考察了M序列反馈函数的线性化矩阵,证明了M序列反馈函数线性化矩阵的2~n阶置换必然是一个2~n阶循环置换。目前,NFSR圈结构和M序列构造仍然是通信和密码系统中的热点与难点问题。本文的研究成果将有助于彻底解决NFSR圈个数分布问题,以及丰富M序列的构造理论,为更深层次的理解NFSR提供思路。