最優(yōu)正規(guī)基下并行乘法器的設(shè)計(jì)*

蘇丹丹，付　萍(.羅定職業(yè)技術(shù)學(xué)院，廣東羅定5700; .北京昌平區(qū)回龍觀中學(xué)，北京000)

最優(yōu)正規(guī)基下并行乘法器的設(shè)計(jì)*

蘇丹丹1，付萍2
(1.羅定職業(yè)技術(shù)學(xué)院，廣東羅定527200; 2.北京昌平區(qū)回龍觀中學(xué)，北京102200)

摘要:利用簡(jiǎn)單的組合邏輯電路分別在Ⅰ型和Ⅱ型最優(yōu)正規(guī)基上設(shè)計(jì)出了新的并行乘法器，其中Ⅰ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為3n－4，與門(mén)數(shù)為n，Ⅱ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為2n－2，與門(mén)數(shù)為n;與Sunar和Koc于2001年在Ⅱ型最優(yōu)正規(guī)基上提出的并行正規(guī)基乘法器對(duì)照，此乘法器大大減少了所需要的門(mén)數(shù)，從而有效地降低了硬件消耗的資源.

關(guān)鍵詞:有限域;最優(yōu)正規(guī)基;乘法器;門(mén)數(shù)

有限域計(jì)算(即加法，減法，乘法和求逆等)被廣泛用于編碼理論，計(jì)算機(jī)代數(shù)學(xué)和密碼學(xué)［1，2］.有限域計(jì)算尤其乘法計(jì)算極大地影響著各種密碼算法的加/解密速度，因此，設(shè)計(jì)性能優(yōu)越的乘法器顯得尤其重要.各種乘法器的算法極大地依賴(lài)于有限域基的選擇.有限域有多種基，如多項(xiàng)式基、正規(guī)基等.在這些基中，使用正規(guī)基對(duì)算術(shù)操作的硬件執(zhí)行是非常有效的.1986年，Omura和Massey首次在文獻(xiàn)［3］中提出正規(guī)基乘法器.

根據(jù)Menezes在文獻(xiàn)［1］中所列舉的數(shù)據(jù)，在n∈[2，2 001 ]范圍內(nèi)屬于Ⅰ型最優(yōu)正規(guī)基的m有117個(gè)，屬于Ⅱ型最優(yōu)正規(guī)基的m有319個(gè).因此，研究最優(yōu)正規(guī)基是非常有意義的.盡管Massey-Omura正規(guī)基乘法器對(duì)Ⅰ型和Ⅱ型最優(yōu)正規(guī)基都有效，但所需異或門(mén)數(shù)為2n(n－1).基于Massey-Omura乘法器，2001年，Sunar 和Koc在文獻(xiàn)［4］中在Ⅱ型最優(yōu)正規(guī)基上提出了一種并行正規(guī)基乘法器，其所需異或門(mén)數(shù)為1.5n(n－1)，與門(mén)數(shù)為n2.文中利用簡(jiǎn)單的組合邏輯電路分別在Ⅰ型和Ⅱ型最優(yōu)正規(guī)基上設(shè)計(jì)出新的并行乘法器，其中Ⅰ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為3n－4，與門(mén)數(shù)為n，Ⅱ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為2n－2，與門(mén)數(shù)為n.與Sunar-Koc正規(guī)基乘法器對(duì)照，此乘法器大大減少了所需要的門(mén)數(shù)，從而有效地降低了硬件消耗的資源.

1　相關(guān)引理和定理

引理1［5］設(shè)和為E在F上互為對(duì)偶的兩組基，則對(duì)

任意u∈E，有

引理2［6］設(shè)為E在F上的一組Ⅰ型最優(yōu)正規(guī)基，T=(ti，j)為其乘法表。則當(dāng)

j=0，1，…，n－1時(shí)，有

引理3［7］設(shè)為E在F上的一組Ⅰ型最優(yōu)正規(guī)基，則N的對(duì)偶基為

定理1［8］設(shè)n+1是素?cái)?shù)，q是模n+1的一個(gè)原根，則F上n個(gè)非單位元的n+1次單位根是線性無(wú)關(guān)的，且組成E在F上一組最優(yōu)正規(guī)基，記為，這里α是一個(gè)n+1次本原單位根，稱(chēng)N為E在F上的一組Ⅰ型最優(yōu)正規(guī)基。

引理4［6］設(shè)為F2n在F2上的一組Ⅱ型最優(yōu)正規(guī)基，T=(ti，j)為其乘法表，則

而當(dāng)i=1，2，…，n－2時(shí)，有

引理5［9］設(shè)為F2n在F2上的一組Ⅱ型最優(yōu)正規(guī)基，則N是自對(duì)偶正規(guī)基。

2　算法設(shè)計(jì)

設(shè)X，Y∈F2n，元素X和Y分別用最優(yōu)正規(guī)基N及其對(duì)偶基B表示為

設(shè)二者的乘積用對(duì)偶基表示為

(其中足標(biāo)均取模n的最小非負(fù)剩余).

又由引理1知:

同理有:

其中足標(biāo)均取模n的最小非負(fù)剩余.

其中足標(biāo)均取模n的最小非負(fù)剩余.

情形2:若N為Ⅱ型最優(yōu)正規(guī)基，則由引理4知αα0=α1，ααn－1=αn－1+αt，其中t=0，1，…，n－1且2t+1≡±3 (mod 2n+1).以及i=1，2，…，n－2，有ααi=αm+αk，其中m，k = 0，1，…，n－1，2m≡2i+1(mod 2n+1)，2k≡－(2i+1)(mod 2n+1)，故

又由引理1知:

類(lèi)似地可得:

其中足標(biāo)均取模n的最小非負(fù)剩余.

進(jìn)而由引理5可知N是自對(duì)偶的，故

綜上所述，完成一次乘法計(jì)算需要3步:

(Ⅰ)確定yj0，yj1，…，yjn－1，yjn+1，…，yjn－1及yt，ym0，ym1，…，ymn－3，yk0，從而獲得所需的yi，i=0，1，…，n－1.

22

(Ⅱ)利用(1)，(2)，(3)，(4)式計(jì)算(xy)0，(xy)1，…，(xy)n－1.

(Ⅲ)若N為Ⅰ型最優(yōu)正規(guī)基，利用(3)式把XY在對(duì)偶基B上轉(zhuǎn)換到最優(yōu)正規(guī)基N上表示.

第一步可借助計(jì)算機(jī)工具(使用C/C++/Matlab程序)確定，第二、三步由簡(jiǎn)單的組合邏輯電路實(shí)現(xiàn).第一步簡(jiǎn)單的Matlab程序如下:

輸出結(jié)果為

確定yt，ym0，ym1，…，ymn－3，yk0，yk1，…，ykn－3程序類(lèi)似.

3　算法復(fù)雜度的簡(jiǎn)單分析

若N為Ⅰ型最優(yōu)正規(guī)基，在計(jì)算(xy)i，i=0，1，…，n－1時(shí)，所需的異或門(mén)數(shù)為2n－2，與門(mén)數(shù)為n;在計(jì)算(xy ) 'i，i=0，1，…，n－1時(shí)，所需的異或門(mén)數(shù)為n－2.綜合所需的異或門(mén)數(shù)為3n－4，與門(mén)數(shù)為n.若N為Ⅱ型最優(yōu)正規(guī)基，在計(jì)算(xy)i=(xy ) 'i，i=0，1，…，n－1時(shí)，所需的異或門(mén)數(shù)為2n－2，與門(mén)數(shù)為n.

設(shè)計(jì)將復(fù)雜和消耗資源的工作由計(jì)算機(jī)工具處理(使用C/C++/Matlab程序)，而實(shí)際設(shè)計(jì)的硬件電路最后形式是簡(jiǎn)單的組合邏輯電路，且該最優(yōu)正規(guī)基下的并行乘法器，Ⅰ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為3n－4，與門(mén)數(shù)為n，Ⅱ型最優(yōu)正規(guī)基并行乘法器所需異或門(mén)數(shù)為2n－2，與門(mén)數(shù)為n.

參考文獻(xiàn):

［1］MENEZES A J.Applications of Finite Fields［M］.Boston:Kluwer Academic，1993

［2］LIDL R，NIEDERREITER H.Introduction to Finite Fields and Their Applications［M］.New York:Cambridge University Press，1994

［3］OMURA J，MASSEY J.Computational Method and Apparatus for Finite Field Arithmetic.US Patent Number 4587627［P］.1986

［4］SUNAR B，KOC C K.An Efficient Optimal Normal Basis TypeⅡmultiplier［J］.IEEE Trans on Computer，2001，50(5):83-87

［5］GEISELLMANN W，GOLLMANN D.Duality and Normal Basis Multiplication［J］.Cryptography and CodingⅢ，1991(187):195

［6］廖群英，孫琦.有限域上最優(yōu)正規(guī)基的乘法表［J］.數(shù)學(xué)學(xué)報(bào)，2005，48(5):947-954

［7］WAN Z X，ZHOU K.On the Complexity of the Dual Basis of a TypeⅠOptimal Normal Basis［J］.Finite Fields and Their Applications，2007，13:411-417

［8］MULLIN R，ONYSZCHUK I，VANSTONE S，et al.Optimal Normal Bases in GF(pn)［J］.Discrete Applied Math，1988-1989，22:149-161

［9］LIAO Q Y，SUN Q.Normal Bases and Their Dual-bases Over Finite Fields［J］.Acta Mathematica Sinica，English Series，2006，22 (3):845-848

Parallel Multiplier Design based on optimal Normal Basis

SU Dan-dan，F(xiàn)U Ping
(1.Luoding Polytechnic，Luoding 527200，China; 2.Beijing Changping Huilongguan School，Beijing 102200，China)

Abstract:A new parallel multiplier is designed by simple combinational logic circuits based on type I optimal normal basis and typeⅡoptimal normal basis respectively.For the type I optimal normal basis，the parallel multiplier needs 3n-4 XOR gates and n AND gates，for the typeⅡoptimal normal basis，the parallel multiplier needs 2n-2 XOR gates and n AND gates.Compared with the normal basis parallel multiplier based on typeⅡoptimal normal basis proposed by Sunar and Koc in 2001，this multiplier greatly reduces required gates so as to effectively decrease the resources of consumption.

Key words:finite fields; optimal normal basis; multipliers; gates

中圖分類(lèi)號(hào):O154.2

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1672－058X(2015) 08－0014－05

doi:10.16055/j.issn.1672－058X.2015.0008.004

收稿日期:2015－05－08;修回日期:2015－06－20.

*基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(10990011).

作者簡(jiǎn)介:蘇丹丹(1980-)，女，湖北隨州人，講師，碩士研究生，從事應(yīng)用數(shù)論研究.