蘇丹丹

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

基于擴(kuò)展多項(xiàng)式集的一種串行乘法器設(shè)計(jì)*

蘇丹丹

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

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

有限域；多項(xiàng)式集；乘法器；復(fù)雜性

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

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

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

1 相關(guān)概念和定義

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

定義2 當(dāng)N={1,α,…,αn-1}是F2n在F2上的多項(xiàng)式基時(shí)，稱N′={1,α,…,αn-1,αn}為擴(kuò)展多項(xiàng)式集.

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

2 算法原理

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

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

對(duì)?a∈F2n，其多項(xiàng)式基表示為

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

?A∈F2n，用擴(kuò)展多項(xiàng)式集表示為

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)式用矩陣表示為

因?yàn)榫仃嚪匠讨泻琻+1個(gè)向量，所以包含n+1個(gè)輸入門和n個(gè)異或門.

從而

(2)

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

根據(jù)上述算法,設(shè)計(jì)的乘法器結(jié)構(gòu)如圖1所示.

圖1 基于擴(kuò)展多項(xiàng)式集上的乘法運(yùn)算實(shí)現(xiàn)過程

利用擴(kuò)展多項(xiàng)式集表示元素，使得乘積運(yùn)算簡(jiǎn)便快捷，在乘法器的設(shè)計(jì)中減少了硬件的消耗，僅需異或門數(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)工程與電子技術(shù),2005,27(8)：65-69.

[5] 曾曉洋，魏仲慧，郝志航.弱對(duì)偶基下比特并行RS編碼器的設(shè)計(jì)[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ù)學(xué)分析原理[M].英文版.北京：機(jī)械工業(yè)出版社，2004.

(責(zé)任編輯 向陽潔)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(10990011);四川省杰出青年學(xué)術(shù)帶頭人培育計(jì)劃項(xiàng)目(2011JQ0037)

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

TP301.1

A

10.3969/j.issn.1007-2985.2014.03.007