一種基于中國(guó)剩余定理的高效乘法器設(shè)計(jì)

崔馨園 李銀 袁華強(qiáng)

(東莞理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523808)

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

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

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

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

1 相關(guān)工作

1.1 中國(guó)剩余定理(CRT)

(1)

1.2 相關(guān)引理

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

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

引理1[12]設(shè)a、b是有限域F2[x]上的多項(xiàng)式，次數(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 乘法器實(shí)現(xiàn)

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

設(shè)f(x)是環(huán)F2[x]上的不可約多項(xiàng)式，A、B是多項(xiàng)式基上任意兩個(gè)多項(xiàng)式，且A,B∈GF(2m)， 將A,B的有限域乘法記為：ABmodf(x)。另設(shè)F(x)=L1f(x)+L2，其中L1、L2∈F2[x]，degree(L1)=l1、degree(L1)=l2。通用公式的設(shè)計(jì)思想關(guān)鍵是不直接計(jì)算ABmodf(x)，而先計(jì)算更容易求得的AB關(guān)于F(x)的商Q和余數(shù)R，然后通過(guò)巧妙的轉(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的有限域乘法運(yùn)算被轉(zhuǎn)換為關(guān)于f(x)的商Q和余數(shù)R的計(jì)算，再對(duì)f(x)進(jìn)行模約簡(jiǎn)兩個(gè)運(yùn)算步驟，為了開(kāi)發(fā)高效的CRT混合乘法器，應(yīng)該選擇能使上述計(jì)算更容易的L1和L2。因此，選擇L1、L2時(shí)應(yīng)滿足以下條件：

a)Q和R容易計(jì)算；

b)L2應(yīng)盡量簡(jiǎn)單；

c)對(duì)f(x)進(jìn)行模約簡(jiǎn)的步驟容易計(jì)算。

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

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

2.1 計(jì)算AB關(guān)于F(x)的商Q：

此時(shí)由于F(x)中包含的項(xiàng)數(shù)不確定，因此不能使用文獻(xiàn)[8]中的Fan計(jì)算方法來(lái)計(jì)算商Q，所以選擇使用文獻(xiàn)[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，使用擴(kuò)展歐幾里得算法易得模逆，該算法公式隨m和k之間的大小關(guān)系變化而變化，最多包含四項(xiàng)。主要有以下幾種情況：

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)不難看出，商的計(jì)算可以在2Tx延遲中實(shí)現(xiàn)。相反，如果m> 6k，revm+k(F(x))-1超過(guò)四項(xiàng)，會(huì)導(dǎo)致商的計(jì)算更復(fù)雜，因此只考慮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 計(jì)算AB關(guān)于F(x)的余數(shù)R

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

(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算法計(jì)算過(guò)程如下：

(9)

3k

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

(10)

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

(11)

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

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

3k

(12)

4k

(13)

(14)

3 時(shí)間和空間復(fù)雜度分析

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

3.1 時(shí)間復(fù)雜度分析

先從3k

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

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

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

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

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

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

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

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

4k

5k

3.2 空間復(fù)雜度分析

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

(15)

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

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

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

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

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

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

3.3 與主流乘法器的比較

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

4 結(jié)語(yǔ)

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

表2 特殊五項(xiàng)式的復(fù)雜度比較