使用de Bruijn图递归构建高级M序列方法

"这篇论文提出了一种基于de Bruijn图的M序列递归升级构造方法，通过利用图论中的Hamilton回路和Euler回路，有效地生成高级M序列。这种方法适用于信息安全领域的应用，因为M序列具有优秀的伪随机性和安全性。论文通过NIST SP800-22随机数测试验证了生成的M序列的高质量。" 正文: M序列（M-sequences），也称为最长线性反馈移位寄存器（Maximum Length Linear Feedback Shift Register, MLFSR）序列，是密码学和通信中广泛使用的一种伪随机数生成器。这些序列因其良好的统计特性，如周期长、自相关低和平衡性，而在加密算法、数据隐藏、通信信道编码等方面有着重要应用。 de Bruijn图是一种特殊的图论结构，其中每个节点代表一个二进制字符串，每条边连接的两个节点代表一个字符串的前缀与后缀。在de Bruijn图中，Hamilton回路是指能够遍历图中所有节点且仅经过每条边一次的路径，而Euler回路则是可以经过每条边恰好一次但不需返回起点的路径。 论文提出的构造方法基于这样的原理：对于n级de Bruijn图，可以通过其内的一条Hamilton回路构造出一个n级M序列；而一条n级M序列可以通过特定操作转化为de Bruijn图中的Hamilton回路。然后，通过寻找这条Hamilton回路的补路，即所有未被包含的边，可以得到一条Euler回路。Euler回路进一步可以用于构建一个n+1级的M序列。通过这种方式，可以递归地生成更高阶的M序列。 这个方法的优点在于它提供了一个从已知的M序列出发，高效生成更高级别M序列的途径，这对于需要大量高级M序列的应用场景非常有用。同时，这种方法的理论基础扎实，利用了图论中的经典概念，使得构造过程有很好的数学保证。 为了验证所生成M序列的质量，论文采用了NIST SP800-22随机性测试套件进行测试。NIST SP800-22是国际上认可的随机数质量评估标准，包括了多项统计测试，如频率测试、块频测试、 Runs测试、Rank测试等，旨在检测生成的序列是否具有良好的随机性质。测试结果表明，使用该方法生成的M序列在所有测试中表现优秀，满足了随机性的要求。 这篇论文的贡献在于提供了一种基于图论的创新方法来生成高级M序列，这不仅有助于提高序列生成的效率，也为信息安全提供了更为强大的工具。通过理论分析和实际测试，证明了这种方法的有效性和可靠性。