使用de Bruijn图递归构建高级M序列方法
需积分: 10 12 浏览量
更新于2024-08-11
收藏 535KB PDF 举报
"这篇论文提出了一种基于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序列,这不仅有助于提高序列生成的效率,也为信息安全提供了更为强大的工具。通过理论分析和实际测试,证明了这种方法的有效性和可靠性。
2021-10-04 上传
2021-02-22 上传
论文
2023-06-01 上传
2023-06-06 上传
2023-06-01 上传
2023-06-01 上传
2023-06-06 上传
2023-06-01 上传
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38552871
- 粉丝: 15
- 资源: 943
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命