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

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

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

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

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

有限域計算(即加法，減法，乘法和求逆等)被廣泛用于編碼理論，計算機(jī)代數(shù)學(xué)和密碼學(xué)［1，2］.有限域計算尤其乘法計算極大地影響著各種密碼算法的加/解密速度，因此，設(shè)計性能優(yōu)越的乘法器顯得尤其重要.各種乘法器的算法極大地依賴于有限域基的選擇.有限域有多種基，如多項式基、正規(guī)基等.在這些基中，使用正規(guī)基對算術(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個，屬于Ⅱ型最優(yōu)正規(guī)基的m有319個.因此，研究最優(yōu)正規(guī)基是非常有意義的.盡管Massey-Omura正規(guī)基乘法器對Ⅰ型和Ⅱ型最優(yōu)正規(guī)基都有效，但所需異或門數(shù)為2n(n－1).基于Massey-Omura乘法器，2001年，Sunar 和Koc在文獻(xiàn)［4］中在Ⅱ型最優(yōu)正規(guī)基上提出了一種并行正規(guī)基乘法器，其所需異或門數(shù)為1.5n(n－1)，與門數(shù)為n2.文中利用簡單的組合邏輯電路分別在Ⅰ型和Ⅱ型最優(yōu)正規(guī)基上設(shè)計出新的并行乘法器，其中Ⅰ型最優(yōu)正規(guī)基并行乘法器所需異或門數(shù)為3n－4，與門數(shù)為n，Ⅱ型最優(yōu)正規(guī)基并行乘法器所需異或門數(shù)為2n－2，與門數(shù)為n.與Sunar-Koc正規(guī)基乘法器對照，此乘法器大大減少了所需要的門數(shù)，從而有效地降低了硬件消耗的資源.

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

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

任意u∈E，有

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

j=0，1，…，n－1時，有

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

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

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

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

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

2　算法設(shè)計

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

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

(其中足標(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知:

類似地可得:

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

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

綜上所述，完成一次乘法計算需要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)式計算(xy)0，(xy)1，…，(xy)n－1.

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

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

輸出結(jié)果為

確定yt，ym0，ym1，…，ymn－3，yk0，yk1，…，ykn－3程序類似.

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

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

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

中圖分類號:O154.2

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

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

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

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

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

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