非线性反馈移位寄存器序列子簇的研究

This project will study sub-families of NFSR sequences, including the existence and the computation of linear sub-families, common sub-families and nonlinear sub-families, and equivalence relation between Galois NFSRs and Fibonacci NFSRs. Algebraic properties of NFSR sequences have been proven extremely resistant to analysis, and many basic properties of NFSR sequences are essentially unknown. By investigating these basic problems on sub-families of NFSR sequences, the relationship between algebraic properties of a family of NFSR sequences and their nonlinear feedback function could be further disclosed, and new research methods and mathematical tools could be explored, which is important for the further research on NFSR sequences.

本申请项目研究非线性反馈移位寄存器(NFSR)的子簇问题。研究内容主要包括NFSR的线性子簇的存在性和求取、公共子簇的存在性和求取、非线性子簇的存在性和求取以及Galois NFSR与Fibonacci NFSR之间的关系。NFSR序列的研究难度非常大，长期以来该领域的许多基本的问题仍未解决。本项目的研究问题都是有关NFSR序列的基本代数性质，通过研究这些问题，一方面，可以对NFSR序列的代数性质与非线性反馈函数之间的关系有一个更清晰认识；另一方面，通过对这些基本问题的研究和思考，试图探索研究NFSR序列的有效方法和数学工具，这对于NFSR序列的进一步研究非常重要。

非线性反馈移位寄存器(NFSR)已广泛应用于密码算法设计，但NFSR序列的基本理论还没有取得重要突破。本项目研究NFSR的子簇、串联、以及Galois NFSR与Fibonacci NFSR之间的关系等问题。具体研究了不可约NFSR的密度、NFSR的线性或仿线性子簇及其求取、NFSR的串联分解、基于NFSR的序列密码算法分析、NFSR 的公共子簇、Galois NFSR与Fibonacci NFSR的等价性、反馈函数为对称布尔函数的NFSR的圈结构、De Bruijn序列特征函数的性质及必要条件等问题。对各个研究内容都取得的很好的研究成果，特别是给出了不可约NFSR的密度的估计、仿射子簇上界的估计以及了将一个NFSR分解为一个NFSR到LFSR串联的算法等，这些结果得到学术界充分肯定。在研究方法上更多在倾向于代数方法，使得对NFSR序列的代数性质与非线性反馈函数之间的关系有一个更清晰认识。另外，通过对本项目的研究，我们探索了对NFSR序列研究的一些有效代数方法和工具，这对于NFSR序列的进一步研究非常重要。