有限域GF(2~m)高效乘法器设计

论文摘要

有限域GF（2m）在密码学和纠错码等领域有许多重要的应用.在GF（2m）定义的算术运算中,乘法是最重要的一种运算,因为其它的运算（例如幂运算和求逆运算）都可以用乘法运算来实现,因此设计高效的乘法器是非常重要的.2013年Cilardo提出了广义多项式基（Generalized Polynomial Basis,GPB）的概念,并给出C.1型和C.2型不可约五项式.2014年Xiong等人构造出了C.1型不可约五项式的高效平方器,其复杂度达到了当前最好的结果.目前关于这两类五项式的乘法器都考虑了时间复杂度优化问题,但对于时间和空间复杂度的权衡考虑的还较少.本文结合Cilardo给出的参数,在Xiong工作的基础上构造出C.2型五项式的平方器,进而针对上述两类五项式设计出高效的时-空权衡乘法器,具体工作如下:1.构造C.2型五项式的高效GPB平方器.根据GF（2m）上的C.2型五项式参数的奇偶性将它们重新分为特定的几类,给出不同分类下所有多项式具体的GPB平方公式,并且证明了新构建的平方器达到了目前最好的结果,最少只需（2m+k1-3）/2的异或门,时延为2TX;2.构造C.1型五项式的Montgomery乘法器.本文在GPB的基础上结合分治算法,针对GF（2m）域上的C.1型不可约五项式提出了一个低复杂度的比特并行Montgomery乘法器.该方法可以将域乘法分解为子多项式乘法和Montgomery/GPB平方,因此所构造出来的乘法器可以节省1/4逻辑门,而且它的时间复杂度与以前使用分治算法构造的乘法器结果基本一致;3.构造一种特殊的C.2型五项式的Montgomery乘法器.本文使用PCHS分治算法,它可以根据多项式的项的奇偶性对它们进行分类.在GPB平方的基础上选定新的参数R,这一参数的选择是由于其赖于C.2型五项式的最小项的阶（非常数）,进而在新的参数的基础上构造出该多项式对应的乘法器并给出了具体的乘法公式。

论文目录

• 摘要
• Abstract
• 第一章 引言
•   1.1 研究背景及研究现状
•   1.2 预备知识
•     1.2.1 有限域
• m）上的Montgomery乘法'>    1.2.2 GF（2^m）上的Montgomery乘法
• m）上的Montgomery平方'>    1.2.3 GF（2^m）上的Montgomery平方
•     1.2.4 PCHS方法及其扩展
• m）上五项式的GPB平方'>    1.2.5 GF（2^m）上五项式的GPB平方
•   1.3 本文主要工作及组织结构
• 第二章 C.1型、C.2型五项式高效平方器构造
•   2.1 C.1型五项式平方器构造
•   2.2 C.2型五项式平方器构造
•   2.3 小结
• 第三章 C.1型五项式的Montgomery乘法器
•   3.1 算法基本思路
• 1B₁,A₂B₂,CD的复杂度'>    3.1.1 A₁B₁,A₂B₂,CD的复杂度
• 1,S₂,S₃的计算'>    3.1.2 S₁,S₂,S₃的计算
•   3.2 复杂度分析及比较
•   3.3 小结
• 第四章 一种特殊C.2型五项式的高效乘法器
•   4.1 算法基本思路
• 1的计算.'>    4.1.1 S₁的计算.
• 2的计算'>    4.1.2 S₂的计算
• 3的计算及复杂度分析'>  4.2 S₃的计算及复杂度分析
•   4.3 小结
• 致谢
• 参考文献
• 攻读学位期间获得与学位论文相关的科研成果目录

文章来源

类型: 硕士论文

作者: 陈晴

导师: 祁传达,李银

关键词: 广义多项式基,平方器,乘法器,型五项式

来源: 信阳师范学院

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机硬件技术

单位: 信阳师范学院

分类号: O157.4;TP332.22

总页数: 60

文件大小: 2538K

下载量: 47