最優正規基下并行乘法器的設計*

蘇丹丹，付　萍(.羅定職業技術學院，廣東羅定5700; .北京昌平區回龍觀中學，北京000)

最優正規基下并行乘法器的設計*

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

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

關鍵詞:有限域;最優正規基;乘法器;門數

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

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

1　相關引理和定理

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

任意u∈E，有

引理2［6］設為E在F上的一組Ⅰ型最優正規基，T=(ti，j)為其乘法表。則當

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

引理3［7］設為E在F上的一組Ⅰ型最優正規基，則N的對偶基為

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

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

而當i=1，2，…，n－2時，有

引理5［9］設為F2n在F2上的一組Ⅱ型最優正規基，則N是自對偶正規基。

2　算法設計

設X，Y∈F2n，元素X和Y分別用最優正規基N及其對偶基B表示為

設二者的乘積用對偶基表示為

(其中足標均取模n的最小非負剩余).

又由引理1知:

同理有:

其中足標均取模n的最小非負剩余.

其中足標均取模n的最小非負剩余.

情形2:若N為Ⅱ型最優正規基，則由引理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知:

類似地可得:

其中足標均取模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為Ⅰ型最優正規基，利用(3)式把XY在對偶基B上轉換到最優正規基N上表示.

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

輸出結果為

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

3　算法復雜度的簡單分析

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

設計將復雜和消耗資源的工作由計算機工具處理(使用C/C++/Matlab程序)，而實際設計的硬件電路最后形式是簡單的組合邏輯電路，且該最優正規基下的并行乘法器，Ⅰ型最優正規基并行乘法器所需異或門數為3n－4，與門數為n，Ⅱ型最優正規基并行乘法器所需異或門數為2n－2，與門數為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］廖群英，孫琦.有限域上最優正規基的乘法表［J］.數學學報，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，FU 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

文獻標識碼:A

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

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

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

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

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