椭圆曲线密码算法(Elliptic Curve Cryptography, ECC)作为公钥密码学中的一个研究重点,在性能、安全方面都被证明有很大的优势。ECC的有效实现依赖于椭圆曲线群上的点乘和点加运算的效率,而这两种运算则直接取决于定义曲线的有限域算术运算的快速实现。有限域包括三种:素域GF(p),二元扩域GF(2~m),一般扩域GF(p~m) (p>2)。目前对有限域算术运算的实现方法主要是根据定义设计的,存在着算法效率不高,资源消耗较多等问题。本文针对上述问题,对ECC所使用的有限域GF(2~m)和GF(p~m)的算术运算实现进行了深入的研究,并且提出了有效的解决方案。本文的研究内容主要包括以下四个方面:首先,对GF(p~m)的乘法快速实现进行了研究。重点研究了基于中国剩余定理(Chinese Remainder Theorem, CRT)对模乘的优化实现。利用二项式剩余算术(Binomial Residue, BR)较为简单的特点,提出了GF(p~m)元素一种新的表示方法,即BR表示,给出了对应的BR-Montgomery乘法;针对最优扩域(Optimal Extension Fields, OEF)所使用的不可约二项式存在数量较少的问题,利用BR表示构造了一类不可约多项式,并对其存在的数量和分布进行了预测,随后研究了模乘的快速实现;使用快速傅利叶变换(Fast Fourier Transform, FFT)进一步提升了BR-Montgomery乘法的实现速度,并使用相应的技巧优化了NTRU (Number Theory Research Unit)密码算法的实现。其次,研究了BR表示下GF(p~m)的求逆运算。提出了一种广义欧几里德算法的变形,进一步完善基于BR表示的算术运算系统;通过对不可约二项式进行变换,提出了一种新的快速模乘算法,并研究了在BR表示下基于Frobenius映射的求逆算法。再次,研究了GF(2~m)的并行乘法器设计。重点研究了基于Karatsuba-Offman算法的乘法器:提出了一种Karatsuba算法的变形,在增加少量电路门的前提下,减小了整个乘法器的时延;结合移位多项式基(Shifted Polynomial Basis, SPB)与Karatsuba算法,构造了两类针对特殊三项式的并行乘法器,与已有的乘法器相比,空间和时间复杂度的综合指标要优于已有的结果。最后,提出了三种基于Fermat小定理的GF(2~m)的求逆算法:基于四次方的Itoh-Tsujii (IT)算法以及Takagi-Yoshiki-Takagi (TYT)算法的两种改进算法。其中,前一种算法使用快速四次方运算代替平方运算,减少了求逆算法的时延;后两种算法则在不同环境下比原TYT算法使用更少的操作。本文创新性的工作描述如下:1.基于二项式剩余算术,提出了GF(p~m)元素的BR表示;据此构造了BR-Montgomery乘法,其计算复杂度为亚平方数量级,最低可达到O(m1.5);针对BR表示提出了一种广义欧几里德的算法变型,可在该表示下直接进行求逆。2.利用BR表示构造了一类不可约多项式,提出了一种模乘的快速实现算法;这种多项式与OEF通常使用的不可约二项式相比,存在数量更多、分布更广,并且模乘效率在某些情况下更高,有效的扩展了OEF的应用范围。3.在对Karatsuba算法进行扩展的基础上,提出了一种基于不可约三项式的Karatsuba算法变型,主要目的在于减少Karatsuba并行乘法器的时延。该乘法器可达到与Mastrovito并行乘法器相同的时延,且空间复杂度更低。此外,提出了两类关于特殊三项式的Karatsuba乘法器,这两种乘法器在达到目前现有并行乘法器最少时延的前提下,空间复杂度仅为同类乘法器的66%和62%,其空间和时间复杂度综合指标达到了最优。4.提出了一种快速四次方运算,并据此改进了IT算法,减少了IT算法的时延。5.推广和改进了TYT求逆算法:提出了一种多项式基下的TYT算法,证明了该算法实际效率至少相当于原TYT算法。此外,利用中间值复用的方法改进了TYT的分解技巧,并进一步减少了求逆运算所需乘法的数量;实验结果表明,改进算法的计算复杂度对部分GF(2~m)的求逆达到了理论下界。