擴(kuò)域的乘法及其快速實(shí)現(xiàn).pdf

1、有限域及其擴(kuò)域的算術(shù)運(yùn)算，是許多差錯(cuò)控制系統(tǒng)的重要模塊。例如，具有強(qiáng)大糾錯(cuò)能力的Reed-Solomon碼就是建立在有限域上的運(yùn)算來完成編碼、解碼的功能。有限域的乘法運(yùn)算效率對(duì)于多種密碼應(yīng)用起著至關(guān)重要的作用，這是一個(gè)值得研究并已被廣泛研究的課題。本文主要研究有限擴(kuò)域的乘法及其快速實(shí)現(xiàn)。
　　 有限域的乘法是有限域運(yùn)算中最重要的一種運(yùn)算，也是極其復(fù)雜和耗費(fèi)時(shí)間的運(yùn)算，而求逆、除法、求冪運(yùn)算都可以轉(zhuǎn)化為乘法運(yùn)算。所以，提高有限域的

2、乘法的運(yùn)算效率對(duì)于整個(gè)密碼方案的實(shí)現(xiàn)具有重要的作用。
　　 經(jīng)典的Karatsuba算法是研究在一般形式上的乘法運(yùn)算，與傳統(tǒng)的多項(xiàng)式乘法相比，所需乘法次數(shù)明顯減少。Montgomery利用中國(guó)剩余定理(CRT)并結(jié)合Winograd短卷積算法討論了在GF(2n)上的多項(xiàng)式乘法，此算法比Karatsuba算法又有比較大的效率改進(jìn)。本文討論在擴(kuò)域GF(Pn)上的快速乘法算法，通過分析快速模約簡(jiǎn)算法、求逆算法、中國(guó)剩余定理(CRT)、