崔馨園 李銀 袁華強

(東莞理工學院 計算機科學與技術學院，廣東東莞 523808)

有限域GF(2m)算術運算在橢圓曲線密碼系統(tǒng)(ECC)、編碼理論和密碼學中具有重要應用價值[1]。有限域算術運算中包含了加、減、乘、除、冪和求逆等多種運算，其中冪運算和求逆運算又可將其轉(zhuǎn)化為乘法運算，由此可見乘法運算是有限域算術運算中最常用的運算方式之一[2-4]。在計算機技術發(fā)展日新月異的今天，計算機需要處理的數(shù)據(jù)呈指數(shù)增長，人們對計算機運算速度的要求也逐漸提高。若能優(yōu)化乘法器的結(jié)構(gòu)，降低有限域乘法算法的開銷，并均衡算法的時間復雜度和空間復雜度，對提高有限域乘法運算的運算速度至關重要。因此，設計高效的有限域乘法算法對有限域算術運算的廣泛應用以及對提高密碼學領域的實用性能都具有重要意義。

有限域乘法器按每個時刻處理的比特數(shù)不同而分成：比特并行乘法器、比特串行乘法器和數(shù)字并行乘法器，其中比特并行乘法器在研究乘法器優(yōu)化領域上應用范圍最廣[5]。根據(jù)乘法器的空間復雜度，比特并行乘法器分為三種類型，分別是平方級比特并行乘法器(Quadratic Bit-Parallel Multiplier)、亞平方級比特并行乘法器(Subquadratic Bit-Parallel Multiplier)和混合型比特并行乘法器(Hybrid Bit-Parallel Multiplier)。平方級比特并行乘法器時間復雜度最低，亞平方級比特并行乘法器空間復雜度最低，而混合型比特并行乘法器可以在時間和空間復雜度之間進行權(quán)衡[3]。有限域乘法器若按有限域基的表示方式又可分為：多項式基、正規(guī)基、對偶基等[6]。若采用多項式基表示方式，則有限域的算術運算也是對應多項式的運算，那么有限域乘法可以分成以下兩個步驟：1)兩個多項式相乘，2)步驟1)的結(jié)果對不可約多項式f(x)取模[7]。其中，步驟2)的復雜程度由多項式f(x)的類型選擇不同來決定，最常使用的不可約多項式為三項式和五項式。本文采用多項式基表示方式，選取的f(x)類型為不可約五項式，對混合型比特并行乘法器進行優(yōu)化設計。

多項式基混合乘法器通常在多項式乘法部分采用分治算法。Karatsuba算法(KA)是最常用的分治算法，與最快的平方級乘法器相比，這些基于KA的混合乘法器通常需要至少一個TX，其中TX是一個2輸入XOR門的延遲。除KA外，其他著名的分治算法，如Winograd短卷積算法和中國剩余定理(CRT)，也廣泛應用于開發(fā)并行乘法器。

2015年Fan首次將中國剩余定理(CRT)運用到乘法器的設計[3]，提出了一種新的有限域乘法運算方法。他在步驟1)采用了傳統(tǒng)的方法，步驟2)沒有采用經(jīng)典的KA算法，而是創(chuàng)新性的提出了使用中國剩余定理(CRT)計算。Fan的架構(gòu)可以為某些特定m階范圍內(nèi)的不可約三項式找到最快的比特并行乘法器，使其具有與最快的比特并行乘法器相同的時間復雜度，并能降低它們的空間復雜度。2017年Zhang和Fan進一步優(yōu)化了該結(jié)果[7]。筆者研究Fan研究結(jié)果發(fā)現(xiàn)，基于中國剩余定理(CRT)的乘法器關鍵思想在于：將步驟2)模約簡轉(zhuǎn)換為對f(x)的非常數(shù)部分取模求得的商和余數(shù)的計算。但文獻[8]和文獻[9]的乘法器僅適用于部分不可約三項式，對范圍更廣的不可約五項式并不適用。為擴大基于CRT的乘法器算法適用范圍，2021年Li與筆者選擇為部分不可約五項式設計基于CRT的更高效的混合型比特并行乘法器[10]，結(jié)果表明，除了不可約三項式外，其他特殊的多項式也能具有適合應用CRT和開發(fā)高效混合乘法器的適當結(jié)構(gòu)。在此過程中，發(fā)現(xiàn)若能設計一個通用的公式，對滿足優(yōu)化條件的f(x)都能采用此通用公式來設計與其對應的CRT乘法器，那么將使基于CRT的乘法器構(gòu)造更一般化。這為本文研究提供了方向，也是本文提出的乘法器模型的理論基礎。

1 相關工作

1.1 中國剩余定理(CRT)

(1)

1.2 相關引理

定義1設a=anxn+an-1xn-1+…+a1x+a0，a屬于有限域F2[x]，則a的反轉(zhuǎn)定義為revk(a)=xka(1/x)。當k=n時，rev(a)表示的是將a系數(shù)反轉(zhuǎn)后的多項式：

rev(a)=revn(a)=a0xn+a1xn-1+…+an-1x+an.

引理1[12]設a、b是有限域F2[x]上的多項式，次數(shù)分別為n，l且(n>l)。q、r分別為a除以b得到的商和余數(shù)，則：

revn-l(q)≡revn(a)revl(b)-1modxn-l+1

結(jié)合引理1可以得出求商Q的通用公式：

Q=revn-l(revn-l(Q))，R=a-Qb.

(2)

2 乘法器實現(xiàn)

筆者在乘法器的設計環(huán)節(jié)未采用文獻[8]和文獻[9]的方法，而是設計了一個通用公式來搭建基于CRT的混合乘法器模型。下面將對通用公式進行說明。

設f(x)是環(huán)F2[x]上的不可約多項式，A、B是多項式基上任意兩個多項式，且A,B∈GF(2m)， 將A,B的有限域乘法記為：ABmodf(x)。另設F(x)=L1f(x)+L2，其中L1、L2∈F2[x]，degree(L1)=l1、degree(L1)=l2。通用公式的設計思想關鍵是不直接計算ABmodf(x)，而先計算更容易求得的AB關于F(x)的商Q和余數(shù)R，然后通過巧妙的轉(zhuǎn)化可以求得ABmodf(x)的結(jié)果，如下所示：

A·Bmodf(x)=Q·F(x)+Rmodf(x)=

(L1·f(x)+L2)Q+Rmodf(x)=

L2·Q+Rmodf(x),

(3)

如式(3)所示，A、B的有限域乘法運算被轉(zhuǎn)換為關于f(x)的商Q和余數(shù)R的計算，再對f(x)進行模約簡兩個運算步驟，為了開發(fā)高效的CRT混合乘法器，應該選擇能使上述計算更容易的L1和L2。因此，選擇L1、L2時應滿足以下條件：

a)Q和R容易計算；

b)L2應盡量簡單；

c)對f(x)進行模約簡的步驟容易計算。

很明顯，在這三個條件中，條件a)依賴于F(x)的計算公式，而b)和c)主要依賴于f(x)的選取，由此更凸顯了選取f(x)的重要性。

綜合考慮以上要求，選擇f(x)=xm+xm-k+xm-2k+x+1這種不可約的五項式，則L1=1、L2=x+1、F(x)=xm+xm-k+xm-2k。套用式(3)，得出有限域乘法的計算公式為：ABmodf(x)=(x+1)Q+Rmodf(x)，接著分別計算出Q和R，再對f(x)模約簡即可求出A、B兩個多項式的有限域乘法運算結(jié)果。

2.1 計算AB關于F(x)的商Q：

此時由于F(x)中包含的項數(shù)不確定，因此不能使用文獻[8]中的Fan計算方法來計算商Q，所以選擇使用文獻[12]中引入的方法，該方法在1.2中介紹了核心引理，套用式(2)可以得到：

revm-l1-2(Q)=

rev2m-2(AB)·revm+l1(F)-1modxm-l1-1，

(4)

由于l1=0，revm+l1(F(x))=revm(F(x))=x2k+xk+1，使用擴展歐幾里得算法易得模逆，該算法公式隨m和k之間的大小關系變化而變化，最多包含四項。主要有以下幾種情況：

revm(F(x))-1=xk+1 2k

revm(F(x))-1=x3k+xk+1

3k+1

revm(F(x))-1=x4k+x3k+xk+1

4k+1

(5)

由式(4)不難看出，商的計算可以在2Tx延遲中實現(xiàn)。相反，如果m> 6k，revm+k(F(x))-1超過四項，會導致商的計算更復雜，因此只考慮2k

revm-2(Q)=rev2m-2(AB)·(xk+1) modxm-1

2k

revm-2(Q)=rev2m-2(AB)·(x3k+xk+1) modxm-1

3k+1

revm-2(Q)=rev2m-2(AB)·(x4k+x3k+xk+1) modxm-14k+1

(6)

3k+1

(7)

2.2 計算AB關于F(x)的余數(shù)R

由于F(x)=xm+xm-k+xm-2k=xm-2k(x2k+xk+ 1)，R的計算可以使用CRT算法來實現(xiàn)。首先，xm-2k和(x2k+xk+ 1)相關的貝祖等式(Bezout identities)根據(jù)m和k之間的大小關系變化而變化：

(x2k+xk+1)·1+xm-2k·(x4k-m+x3k-m)=1

2k

(x2k+xk+1)·(xk+1)+xm-2k·x5k-m=1

3k

(x2k+xk+1)·(x3k+xk+1)+xm-2k·(x7k-m+x6k-m)=1 5k

(8)

因此，余數(shù)R使用CRT算法計算過程如下：

(9)

3k

[AB]xm-2k·(x5k+x4k+1) modF(x)=

(10)

不難看出，[A]x2k+xk+1和[B]x2k+xk+1可以在2Tx時延中并行實現(xiàn)，并能計算出[A]x2k+xk+1和[B]x2k+xk+1所需的XOR門數(shù)：

(11)

2.3 計算有限域乘法的結(jié)果C

將有限域乘法ABmodf(x)記為C， 則C=(x+1)Q+R。因此，C可以通過分別求出R、Q和xQ的結(jié)果并將它們相加得到。為了更有效地計算R，將R的計算公式劃分成R1、R2兩部分求解，可得：

3k

(12)

4k

(13)

(14)

3 時間和空間復雜度分析

分別對設計的乘法器的時間復雜度和空間復雜度進行分析，并將其與主流的同類型乘法器進行比較，同時還介紹了整個乘法器模型構(gòu)建的運算過程，從結(jié)果倒推可知，整個過程從A、B兩個多項式的乘法開始，過程中包含大量對系數(shù)進行的異或運算以及加法運算，分析乘法器模型的時間和空間復雜度，需要從分析AND電路門和XOR電路門的數(shù)量和延時開始，其中對系數(shù)的計算和分析顯得尤為重要。

3.1 時間復雜度分析

先從3k

注意，表1所表示的ti在計算時先分別并行計算gi、hj(0≤i，j≤2k-1)，產(chǎn)生的兩個時延需消耗2TX，因此，把此部分特殊公式用“*”表示。此外，對x2k+xk+1進行多項式乘法的模約簡運算時，相應的乘法矩陣有部分項需要再做一次加法，這部分項在表中用“?”表示。

表1 R1、R2和Q系數(shù)中包含的項數(shù)統(tǒng)計

對x2k+xk+1進行多項式乘法的模約簡運算采用文獻[13]提出的計算方法，通過重新排列計算順序提高速度。如令k=3，需要進行多項式乘法模約簡的算式為C1=A1B1modx6+x3+1，其中A1=a5x5+a4x4+a3x3+a2x2+a1x+a0，B1=b5x5+b4x4+b3x3+b2x2+b1x+b0。因此，該多項式乘法模約簡運算的矩陣向量形式為：

由Z矩陣可以看出，有部分項需要多做一次加法，由于是并行計算，因此此處會產(chǎn)生TA+TX的電路門延時。將所有結(jié)果都采用分治思想，并借鑒二叉樹的思想，將其兩兩異或、并行迭代。為方便表達，下文將這種運算方法簡化表達為異或二叉樹，異或二叉樹運算過程需要「log2(k+「k/2?)?=「log25?=3 XOR延遲。因此，[AB]x2k+xk+1的時間復雜度最高會達到TA+「log2(3k)?TX。實際計算兩個子式和時，可采用與文獻[8,14]一樣的方法，將兩個子式合并到一個異或二叉樹以提高計算速度。

分別評估R1、R2和Q電路門的延時。從表1可以看出，R1中會產(chǎn)生最多電路門延時的是系數(shù)處于r1,m-k-1=sm-2k-1+tm-2k-1時，sm-2k-1是m-2k個項的總和，tm-2k-1需要耗費2TX來計算gi、hi以及1TX用于其中的k項。在此過程中，sm-2k-1的異或二叉樹也可以與tm-2k-1的異或二叉樹合成一個樹并行計算。

TA+「log2((4(5k-m)+2v1))?TX，

v1=「log2(m-3k)?，

同樣，做以上相似的分析也可易得其他情況下的時間復雜度：

4k

5k

3.2 空間復雜度分析

先對R1、R2、Q的系數(shù)進行計算，根據(jù)式(9)和式(10)～式(14)可知，主要是：

(15)

由于si是AB的系數(shù)，因此可以直接得出si的公式為：

得到式(16)中系數(shù)表達式的空間復雜度：

(2k)2=6k2-2km+m2-k，

乘法器所需的AND電路門的數(shù)量等于式(15)中所需的數(shù)量，即6k2-2km+m2-k。而XOR電路門的數(shù)量通過式(7)和式(12)～式(14)可以看出，需要額外的XOR電路門來計算不同子式和C之間的加法，且需要消耗幾個XOR電路門對[A]x2k+xk+1和[B〗x2k+xk+1預計算。最后統(tǒng)計這些操作所需的XOR電路門的數(shù)量如下：

因此，乘法器所需的XOR電路門的總數(shù)為：

分析以上數(shù)據(jù)可知，當m>3k時，AND電路門的數(shù)量會小于m2，換言之，當m>3k時，設計的乘法器所需邏輯電路門的數(shù)量可能比平方級乘法器所需的更少。

3.3 與主流乘法器的比較

文獻[10]中設計的CRT乘法器為當前同類不可約五項式乘法器中最主流的研究成果，本文所構(gòu)造的乘法器與其相比，在時間復雜度略有增加的情況下，空間復雜度有所降低，達到了時間空間復雜度均衡的目的。為了更明顯的表達，更進一步地體現(xiàn)比較結(jié)果，筆者驗證了在[100,1 000]次數(shù)內(nèi)的所有符合不可約五項式xm+xm-k+xm-2k+x+1的結(jié)果，并統(tǒng)計成表格。為方便表達筆者將文獻[10]中的乘法器以作者首字母縮寫命名為LCY。從比較結(jié)果中可知，與主流乘法器相比最多會增加2Tx的時延。

4 結(jié)語

為提高有限域乘法運算的速度，擴大乘法器的應用范圍，使基于中國剩余定理的乘法器架構(gòu)更一般化。筆者設計了一個通用公式來搭建基于中國剩余定理的混合乘法器模型，找到一個特殊的不可約五項式f(x)=xm+xm-k+xm-2k+x+ 1，套用通用公式成功將多項式對f(x)的運算轉(zhuǎn)化成對更簡單的F(x)的商和余數(shù)的計算，其中對余數(shù)的計算延用前人的方法采用中國剩余定理，對商的計算創(chuàng)新性地采用了兩次求逆的方法。該乘法器將時間復雜度和空間復雜度進行了均衡，得到了較優(yōu)的結(jié)果，在時間復雜度稍大于當前最快的并行乘法算法的前提下，空間復雜度得到了優(yōu)化，當m>3k時，本文構(gòu)建的乘法器的空間復雜度比同類型的主流乘法器更低，并且擴大了基于中國剩余定理的乘法器的適用范圍。

表2 特殊五項式的復雜度比較