论文部分内容阅读
有限域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型五项式的最小项的阶(非常数),进而在新的参数的基础上构造出该多项式对应的乘法器并给出了具体的乘法公式。