基于并行计算寻找非线性反馈移位寄存器的方法

发布时间：2017-08-07 07:22

  本文关键词：基于并行计算寻找非线性反馈移位寄存器的方法

  更多相关文章： 非线性反馈移位寄存器 并行计算 GPU MapReduce

【摘要】：在流密码中，非线性反馈移位寄存器（Non-Linear Feedback ShiftRegister，NLFSR）是一种常用的、安全性较高的伪随机序列生成器。目前NLFSR领域一个主要的问题是，没有一种普遍有效的数学算法，能够根据给定的周期，直接推导出符合这个周期条件的所有NLFSR。为了对问题进行研究，就需要大量指定周期的NLFSR的实验数据作为支持。本文主要提出了两种可以快速获取指定周期的NLFSR的编程算法。这两种算法分别是基于GPU并行计算和MapReduce并行计算来实现的。通过并行计算来寻找NLFSR的方法具有性能上的优势，，计算速度快，尤其适用于处理高次数的复杂NLFSR。使用并行计算的方法能够快速大规模地计算出符合条件的NLFSR，能够为未来研究寻找指定周期的NLFSR的数学算法提供大量的实验数据。
【关键词】：非线性反馈移位寄存器 并行计算 GPU MapReduce
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333
【目录】：

• 摘要3-4
• ABSTRACT4-9
• 第一章 绪论9-12
• 1.1 研究背景9-10
• 1.2 国内外研究现状10
• 1.3 目前存在的问题10-11
• 1.4 本文的研究内容及工作11
• 1.5 全文内容结构11-12
• 第二章 反馈移位寄存器与并行计算技术12-30
• 2.1 反馈移位寄存器（FSR）12-17
• 2.1.1 反馈移位寄存器的构造12-13
• 2.1.2 反馈移位寄存器的形式化表示13
• 2.1.3 反馈移位寄存器的工作原理13-14
• 2.1.4 反馈移位寄存器的分类14-15
• 2.1.5 反馈移位寄存器的周期和输出序列15-17
• 2.2 MapReduce 并行计算框架17-24
• 2.2.1 MapReduce 框架的来源和基本概念17-18
• 2.2.2 MapReduce 的计算框架18-20
• 2.2.3 MapReduce 的计算流程20-24
• 2.2.4 MapReduce 的主要适用场景24
• 2.3 GPU 并行计算框架24-30
• 2.3.1 GPU 的结构特征24-26
• 2.3.2 统一计算架构 CUDA26
• 2.3.3 通过 CUDA 进行 GPU 并行计算26-28
• 2.3.4 GPU 并行计算的主要适用场景28-30
• 第三章 基于并行计算框架寻找 NLFSR30-47
• 3.1 实验目标和计算任务30-31
• 3.1.1 计算程序的输入30-31
• 3.1.2 计算的目标结果31
• 3.2 计算流程和算法31-35
• 3.2.1 将 NLFSR 按类型分组31-34
• 3.2.2 使用串行计算来寻找符合条件的 NLFSR34-35
• 3.3 基于单机的 GPU 并行计算实验设计35-39
• 3.3.1 硬件条件与环境35
• 3.3.2 主要的算法与逻辑35-39
• 3.4 基于集群的 MapReduce 并行计算实验设计39-44
• 3.4.1 硬件条件与环境39-40
• 3.4.2 在 MapReduce 框架中计算 NLFSR40-41
• 3.4.3 主要的算法与逻辑41-43
• 3.4.4 对传统 MapReduce 计算框架的革新43-44
• 3.5 两种方案的可行性分析和比较44-46
• 3.6 本章小结46-47
• 第四章 实验结果的比较，验证和分析47-59
• 4.1 计算结果的正确性分析47-52
• 4.1.1 并行计算逻辑的正确性分析47-50
• 4.1.2 算法执行的示例和验证50-52
• 4.2 计算的时间代价分析52-58
• 4.2.1 提升计算速度的重要意义52-53
• 4.2.2 不同框架下计算速度的比较53-56
• 4.2.3 处理高次数复杂 NLFSR 时的性能优势56-58
• 4.3 本章小结58-59
• 第五章 总结59-61
• 第六章 结束语61-63
• 6.1 论文主要工作61
• 6.2 未来工作展望61-63
• 参考文献63-66
• 致谢66-67
• 攻读硕士学位期间已发表或录用的论文67-70
• 附件70

【共引文献】

中国期刊全文数据库 前1条

1 叶炜晨;陈克非;;快速寻找非线性反馈移位寄存器的编程算法[J];计算机科学与探索;2014年01期

本文编号：633444