低复杂度二元扩域多项式基和高斯正规基乘法器设计.doc

低复杂度二元扩域多项式基和高斯正规基乘法器设计有限域GF(2m)乘法器被广泛地应用在椭圆曲线密码体制(ECC,EllipticCurveCryptography)、纠错码和伽罗瓦/计数器模式(GCM,Galois/CounterMode)中。乘法器性能和复杂度决定着这些应用的整体性能和适用性。在乘法器设计方面,基于多项式基和高斯正规基的乘法运算得到了广泛关注。因此本文将在这两个方面进行研究,着眼于高性能、低复杂度,对乘法器设计进行深入研究。本文研究的内容和结果分为下面四部分。1)在有限域GF(2m)中,虽然基于多项式基的乘法运算简单、易于模块化,但是相比较于其它基底乘法器,多项式基乘法运算不仅需要正常的乘法计算,还需要考虑多项式约减模块。为此,约减模块中的不可约多项式通常考虑为特殊类型的多项式,如全一多项式、等间距多项式,以及后来的三项多项式和五项多项式。作为多项式基乘法运算的重要且经典方法,Karatsuba算法能够设计出具有次二次复杂度(Subquadraticcomplexities)的乘法器架构。为此本文在Karatsuba算法基础上,提出了(b,2)分法。接着以(b,2)分法为基础,提出了一种低空间复杂度的字串行乘法器。再结合Karatsuba算法的k分法,提出了一种可扩展的一般化多项式基乘法器架构。根据理论分析,所提的乘法器能够在时间和空间复杂度之间取得平衡。所提出的乘法器具有模块化、有规则的特点,适合于VLSI进行实现。与其它字串行和可扩展乘法器比较,具有低空间复杂度、低时间复杂度和低能量消耗的优点。2)高斯正规基,作为特殊类型的正规基,不仅继承了正规基的最大优点,平方操作只需要系数移位,而且还兼具多项式基的一些特性。通过定义,高斯正规基可转换成回文多项式基表示,偶型高斯正规基乘法运算可表示为两个TMVP(ToeplitzMatrix-VectorProduct)之和的形式。值得注意的是,在所得的两个TMVP中,有一个矩阵是对称的Toeplitz矩阵,在相关文献中并没有充分利用此特性。因此本文对这种对称的Toeplitz矩阵进行研究,提出一种STMVP(SymmetricTMVP)分解。STMVP的二分法能够形成2个乘法点形式,一个是STMVP结构,另一个是TMVP结构。STMVP的三分法则形成5个乘法点,其中2个是STMVP结构,其它3个是TMVP结构。结合TMVP方法,STMVP的二分法和三分法能够实现具有次二次复杂度的乘法器。根据拟合结果,与已有的Karatsuba算法和TMVP分解方法比较,所提的STMVP分解方法具有低空间、低功率、低ADP(Area-DelayProduct)的优点。3)基于回文多项式基表示,偶型高斯正规基乘法也可表示为一个TMVP和一个HMVP之和的形式,可记作C=TA+HA,其中TA为TMVP,HA为HMVP。一种新的矩阵可定义为S=T+H,由于矩阵T是对称的Toeplitz矩阵,矩阵H是Hankel矩阵,因此这种新的矩阵为对称矩阵。因此高斯正规基乘法运算被转换成一个SMVP(SymmetricMatrix-VectorProduct)结构,记作C=SA。利用对称性,SMVP的n分法被提出。基于二分法,SMVP的递归分解形式通过n=4和n=8两个例子进行了详细阐述。在n=4和n=8中,SMVP的递归分解与TMVP的二分法和TMVPBR(TMVPBlockRecombination)方法比较,所需的AND逻辑门和XOR逻辑门是最少的。4)基于回文多项式基表示,偶型高斯正规基乘法可表示为一个TMVP和一个HMVP之和的形式。利用TMVP的二分法,提出了一种HMVP和TMVP之和的方法。再结合回文多项式分解和部分积形式,本文提出了一种字串行高斯正规基乘法器架构。根据理论分析,所提的字串行乘法器具有更低的空间复杂度,并且在时间和空间复杂度之间取得较好的平衡。总之,本文在Karatsuba算法和TMVP方法的基础上,分别提出了(b,2)分法、STMVP分解方法和SMVP分解方法。这三种方法均有益于设计和实现具有高性能、低复杂度有限域乘法器。