摘要: 在公元1985 年Victor Miler与Neal Koblit各自推出椭圆曲线密码系统（elliptic curve　cryptosystem， ECC）。由于ECC 的金钥长度可远较诸如RSA 等其它公钥密码系统为小就可以达到相同的安全强度，这使得ECC 非常适合在行动通讯(如手机)等资源有限环境下使用。也因此ECC是新一代最具厚望的密码学算法，而且近年来也已被广泛地制订于国际标准如FIPS 186-2I、ANSI　X9.62、　IEEE P1363 、SO 11770-3 等。ECC 执行速度快慢的关键是在乘法的效率上。乘法算法的效率又与所选取的场有关，而以效率而言，有限场(Finite fields, Galois field)是目前使用的最普遍的场。近些年来，有限场数值运算被广泛应用在编码理论、计算机密码、数字讯号处理, 逻辑设计, 和随机数产生器等领域上，受到相当大注意。自从H. Kung提出心脏收缩电路架构（systolic architecture）设计观念之后，此观念已被运用至许多不同领域的电路设计上以求简化系统设计过程与提升系统运算速度。尤其是讯号处理、错误控制编码及密码等系统的设计。在有限场的各种运算之中，以加法运算最为简单，而以乘法、指数、及找乘法反元素等运算较为复杂。然而有限场GF(2m)的运算，由于无进位问题必须处理，因此较有限场GF(P)或GF(Pm)中的运算简单而且应用较广。在这些有限场数值运算中最重要的运算动作为乘法运算，因为加法和减法运算只是简单的互斥运算，而更复杂的运算如除法、指数运算、和反元素运算都可以利用乘法的反复运算来解决，因此乘法运算可说是有限场数学最核心之运算动作，乃成重要的研究主题。由于有限场元素的表示法会直接影响到执行的效率，所以有许多专家学者专注在不同的元素表示法，这其中有三种最常被用到的表示法为(1)多项式基底(Polynomial Basis (PB))表示法，(2)正规基底(Normal Basis (NB))表示法，和(3)双重基底(dual basis (DB))表示法。为了使GF(2^m)场中的乘法器易于设计并增快运算速度，Yeh , Reed与Truong三位学者利用多项式基底表示法，于1984年设计了位并列心脏收缩乘法器。此后，有许多的学者相继设计了多种的位并列心脏收缩乘法器，虽然这些电路适用于所有的GF(2m)场，但因电路较复杂而较不适合于m值很大的密码系统。为了降低电路复杂度，Lee et al.于2001年依据All-one polynomial(AOP)及Equally-Spaced Polynomial (ESP)多项式设计了低复杂度位并列心脏收缩乘法器，另外，Lee et al. 以AOP心脏收缩乘法器做为模块，设计了适用于大m值的低复杂ESP心脏收缩乘法器。但AOP多项式在有限场GF(2m)是非常稀少，如m?100，不可分解AOP之m值为2、4、10、 12、18、 28、36、 52、 58、 60、 66、 82、 及 100。根据双重基底表示法，本文提出一新的GF(2m)乘法算法，运用重复使用电路的概念，设计低复杂度的位并列心脏缩收乘法器。以晶体管数来评估电路的面积，与传统的双重基底乘法相比较，设计的乘法器可以省65%电路设计面积。值得注意，已知的低复杂度乘法器是利用AOPs及三项多项式来设计的，提出的乘法器也可省22%电路设计面积。由此可证明，提出的乘法算法具有最低复杂度电路架构，此电路很适合应用于密码系统的硬件设计。