蘇丹丹

(羅定職業(yè)技術學院教育系，廣東 羅定 527200)

基于擴展多項式集的一種串行乘法器設計*

蘇丹丹

(羅定職業(yè)技術學院教育系，廣東 羅定 527200)

基于多項式基定義了擴展多項式集，利用其形式表示有限域F2n中的元素.通過分析多項式集下的乘法運算公式，設計出一種有效的串行乘法器，僅需n個異或門和n+1個門數(shù).

有限域；多項式集；乘法器；復雜性

有限域在編碼理論、計算機通信和密碼學中有廣泛的應用,特別是基于有限域F2n上的橢圓曲線密碼體制以其短密鑰、高強度等優(yōu)點引起人們的高度重視.在橢圓曲線密碼體制中,如AES標準橢圓曲線加密算法、RSA算法等，有限域上的乘法運算極大地影響各種密碼算法的速度.因此,設計復雜性低的有限域的算法和乘法器已成為研究熱點[1].

關于有限域F2n上的乘法器的研究,按照參加運算的元素的形式來分有3種[2]:正規(guī)基、多項式基(或標準基)和對偶基.根據具體的實現(xiàn)方式，分為并行乘法器和串行乘法器.目前,各種形式的乘法器都在不斷被研究和比較.文獻[3]提出一種II型最優(yōu)正規(guī)基并行乘法器設計方案.文獻[4] 基于II型最優(yōu)正規(guī)基設計了一個串行乘法器，但利用最優(yōu)正規(guī)基在計算過程中都需要先將域元素的正規(guī)基表示轉換為多項式基表示,在多項式基下做乘法運算,再將結果轉換為正規(guī)基表示.文獻[5]中提出基于弱對偶基下的比特并行乘法器,這個過程涉及到最優(yōu)弱對偶基的選擇和多項式基與弱對偶基之間的變換.由于對偶基乘法和正規(guī)基乘法中都存在基底轉換問題,因此當有限域的維數(shù)變大時,乘法器的電路規(guī)模將會急劇增大,對橢圓曲線密碼系統(tǒng)設計不宜.選擇利用多項式基設計乘法器,避免了基與基之間的轉換.另一方面,在并行乘法器中，隨著并行的增多，乘法運算和加法運算會增加，往往導致運行速度的下降，而串行乘法器以犧牲運行速度為代價來獲得更好的性能.因此，如何選擇串行或并行乘法器取決于它的應用性質.

筆者在多項式基的基礎上定義了擴展多項式集，利用擴展多項式集形式表示有限域F2n中的元素，打破了傳統(tǒng)的利用移位多項式基底表示元素的方法，避免了多項式基和移位多項式基底的轉換，同時使得任意兩元素相乘得到的結果既簡單又規(guī)則.

1 相關概念和定義

定義1[6]設N={α0,α1,…,αn-1}是F2n在F2上的一組基，若存在β∈F2n，使得αi=βi(0≤i≤n-1),則稱N為一組多項式基，即N形如{1,α,…,αn-1}.

定義2 當N={1,α,…,αn-1}是F2n在F2上的多項式基時，稱N′={1,α,…,αn-1,αn}為擴展多項式集.

定義3[7]系數(shù)全部為1的多項式稱為全一多項式(All￣One￣Polynomial,AOP).次數(shù)為n的AOP多項式為AOP(x)=xn+xn-1+…+x2+x+1，有如下基本性質:(ⅰ)(x-1)AOP(x)=xn+1-1；(ⅱ)AOP多項式是不可約多項式當且僅當n+1是素數(shù),且2是模n+1的本原根.

2 算法原理

域F2n由F2上的n次不可約多項式產生,不可約多項式的選擇在有限域乘法器的執(zhí)行中也扮演著重要角色,為計算簡便，選取AOP多項式.

設f(x)=xn+xn-1+…+x2+x+1 是F2上的一個不可約AOP多項式且α是f(x)的根,F2n=F2/(f(x))，是F2的n次擴域.由代數(shù)知識可知,f(x)是α的極小多項式,且αn+αn-1+…+α=1,αn+1=1.

對?a∈F2n，其多項式基表示為

a=an-1αn-1+an-2αn-2+…+a1α+a0ai∈F2,0≤i≤n-1.

?A∈F2n，用擴展多項式集表示為

A=Anαn+An-1αn-1+…+A1α+A0An=0，Ai∈F2,0≤i≤n-1.

由αn+1=1可知：

又i,j∈[0,n]，于是0≤i+j≤2n，若i+j≡n(modn+1)，則必有i+j=n，即

(1)

記AB=D=D0+D1α+…+Dn-1αn-1+Dnαn.其中：

D0=A1Bn+A2Bn-1+…+An-1B2+AnB1+A0B0,

D1=A2Bn+A3Bn-1+…+AnB2+A0B1+A1B0,

…

Dn=A0Bn+A1Bn-1+…+An-2B2+An-1B1+AnB0.

將(1)式用矩陣表示為

因為矩陣方程中含n+1個向量，所以包含n+1個輸入門和n個異或門.

從而

(2)

記ab=d0+d1α+…+dn-1αn-1.由(1)，(2)式知,(1)式易于用矩陣表示，(2)式如用矩陣表示，方陣中元素是和的形式，較復雜；乘積結果表達式中，(1)式中αi(0≤i≤n)的系數(shù)更簡潔,規(guī)律更明顯,這就決定了采用算法1在實際操作和乘法器設計中呈現(xiàn)較大的優(yōu)勢，用C語言實現(xiàn)的算法如下:

main()

{int A[N]={A0,A1,A2,…,An},

B[N]={B0,B1,B2,…,Bn};

int i,j,k,N=n+1;

int D[N];

for(k=0;k<=N-1;k++)

for(i=0;i<=N-1;i++)

for(j=0;j<=N-1;j++)

{if((i+j)%N=k)

{D[k]=D[k]+A[i]*B[j];}

}

for(k=0;k<=N-1;k++)

{printf(″%d″,D[k]);}

}

3 乘法器設計

根據上述算法,設計的乘法器結構如圖1所示.

圖1 基于擴展多項式集上的乘法運算實現(xiàn)過程

利用擴展多項式集表示元素，使得乘積運算簡便快捷，在乘法器的設計中減少了硬件的消耗，僅需異或門數(shù)為n,與門數(shù)為n+1.

[1] MASOLEH A R.Efficient Algorithms and Architcctures for Field Multiplication Using Gaussian Normal Bases[J].IEEE Transactions on Computers,2006,55(1):34-47.

[2] KOC C K,SUNAR B.Low￣Complexity Bit￣Parallel Canonical Normal Basis Multipliers for a Class of Finite Fields[J].IEEE Transactions on Computers,1998,47(3):353-356.

[3] SUNAR B,KOC C K.An Efficient Optimal Normal Basis Type Ⅱ Multiplier[J].IEEE Transactions on Computers,2001,50(5):83-87.

[4] 王慶先，孫世新,方 冰.基于Ⅱ型最優(yōu)正規(guī)基的串行乘法器[J].系統(tǒng)工程與電子技術,2005,27(8)：65-69.

[5] 曾曉洋，魏仲慧，郝志航.弱對偶基下比特并行RS編碼器的設計[J].光電工程，2001,28(3)：1 494-1 496.

[6] QUTTINEH N H.Computational Complexity of Finite Field Multiplication[M].Examensarbete Utforti Datatransmission vid Linkopings Tekniska Hogskola,Linkoping,2003.

[7] RUDIN W.數(shù)學分析原理[M].英文版.北京：機械工業(yè)出版社，2004.

(責任編輯 向陽潔)

SerialMultiplierBasedonExtendedPolynomialSet

SU Dandan

(Deptartment of Education,Luoding Vocational Polytechnic,Luoding 527200,Guandong China)

The extended polynomial set is defined based on the polynomial basis,which represents the element of the finite fieldF2n.The multiplying formula is analyzed carefully.An efficient serial multiplier is proposed,which needs onlynXOR gates andn+1 AND gates.

finite field;polynomial set;multiplier;complexity

1007-2985(2014)03-0028-03

2013-12-26

國家自然科學基金資助項目(10990011);四川省杰出青年學術帶頭人培育計劃項目(2011JQ0037)

蘇丹丹(1980-)，女，湖北隨州人，羅定職業(yè)技術學院教育系講師，碩士，主要從事應用數(shù)論研究.

TP301.1

A

10.3969/j.issn.1007-2985.2014.03.007