大整數(shù)取模的快速運算

許鑫，李順東

陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院，西安 710062

大整數(shù)取模的快速運算

許鑫，李順東

陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院，西安 710062

1 引言

大整數(shù)取模運算在公鑰密碼學(xué)中具有重要的實際應(yīng)用價值，如RSA[1]算法。在進(jìn)行大量的加密/解密運算時，大整數(shù)取模運算是制約RSA算法效率的主要因素，這使得RSA算法的計算復(fù)雜度較高，在與相同安全級別的對稱加密算法[2]相比時，RSA算法的運算效率很低。因此，在公鑰密碼學(xué)中，對大整數(shù)取模算法的改進(jìn)具有重要的實用價值。傳統(tǒng)的大整數(shù)取模運算步驟主要是一個試商的過程，即每一次試商都需要做一次遍歷，每次遍歷中還需要做乘法和試減運算，使得時間復(fù)雜度為O(n2)，效率很低。因此提出了很多種對大整數(shù)取模運算的改進(jìn)算法，如蒙哥馬利（Montgomery）[3]算法和歐幾里德除法[4]等，但都沒有達(dá)到理想的效果。

本文另辟蹊徑，依據(jù)分治法[5]思想，提出一種改進(jìn)大整數(shù)取模運算的快速算法，將原來的遍歷運算轉(zhuǎn)換成8次大整數(shù)乘法運算和準(zhǔn)確試商運算，使得計算復(fù)雜度降低到O(n(m-n))，極大地提高了大整數(shù)取模運算的效率，從而改進(jìn)和優(yōu)化RSA算法。

2 大整數(shù)取?？焖偎惴?/h2>

2.1 大整數(shù)取模算法

大整數(shù)取模運算需要進(jìn)行乘法和減法兩個步驟，對每一位的商都要重復(fù)這兩個步驟。設(shè)有m位和n位兩個大整數(shù)A和B(m＞n＞1)，取模運算表示成：

首先截取大整數(shù)A的前n位對大整數(shù)B進(jìn)行試減運算，然后將大整數(shù)A的第n+1位添加至余數(shù)的末尾組成新的被除數(shù)，如此循環(huán)，直至最后的余數(shù)小于大整數(shù)B，此時的余數(shù)即是最后的結(jié)果C。算法步驟如下：

其中B1存放試減的數(shù)，C為每次試減后的結(jié)果，for循環(huán)結(jié)束后即為最后的余數(shù)。由于遍歷需要m-n次，每次需要8次乘法，而這8次乘法都是重復(fù)地與大整數(shù)B進(jìn)行相乘，因此，可以用查找表代替重復(fù)運算來改進(jìn)算法。

2.2 改進(jìn)算法的核心思想

大整數(shù)取模是一個運算量極大的數(shù)學(xué)運算，因為當(dāng)n很大時，傳統(tǒng)的大整數(shù)取模算法效率極為低下。蒙哥馬利（Montgomery）算法是將冪模運算[6]轉(zhuǎn)換成乘法和移位運算，雖然最后結(jié)果看似簡單，但是對中間變量的求解是比較復(fù)雜的，尤其在RSA算法中，中間變量的不斷變化也使此算法的效率降低。文獻(xiàn)[7]采用變長滑動窗口方法改進(jìn)的蒙哥馬利算法，雖然提高了模指數(shù)運算，但在大整數(shù)的取模運算中，過多的乘法次數(shù)必然影響其效率。為了提高冪模運算效率，國內(nèi)外專家學(xué)者已經(jīng)提出了很多改進(jìn)的算法[8-10]。

在對公鑰密碼尤其是RSA算法的研究中，可以發(fā)現(xiàn)[11-12]：

（1）模運算的結(jié)果在運算最后直接獲得，不需要另外記錄。

（2）面向公鑰密碼的模運算，每一次的加密/解密運算過程所用到的大整數(shù)n是固定不變的，并且是循環(huán)使用。因此，對其進(jìn)行預(yù)處理，得到一個預(yù)處理表，以便在一次加密/解密過程中多次調(diào)用，從而避免重復(fù)運算所浪費的時間，降低運算復(fù)雜度。

（3）在每次模運算中通過尋找模運算的規(guī)律，可以得到每次快速模運算的方法。

在現(xiàn)實中，整數(shù)是以十進(jìn)制進(jìn)行存儲，乘法計算也是以十進(jìn)制方式表達(dá)的，因此本文提出的大整數(shù)取模改進(jìn)算法，是以十進(jìn)制數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲和運算的。

任何一個正整數(shù)是由0～9中的一個或多個數(shù)字組成，其中首位數(shù)字不能為0。例如：設(shè)存在一個m位和一個n位大整數(shù)A和B(m＞n＞1)，根據(jù)分治法思想，對大整數(shù)A和B做乘法運算時，

文獻(xiàn)[13]提出一種大整數(shù)相乘快速算法：將大整數(shù)A分解為m個獨立整數(shù)的組合，這樣大整數(shù)A和B的乘法運算就是將m個數(shù)字(0～9)與大整數(shù)B的相乘運算得到的結(jié)果存儲在一個查找表數(shù)組Value[10]中，即Value[0]存儲0，Value[1]存儲大整數(shù)B，Value[2]～Value[9]依次存儲數(shù)字2～9和大整數(shù)B的乘積。然后依次根據(jù)大整數(shù)A的m位整數(shù)進(jìn)行查表，將乘法結(jié)果移位后做加法運算得到最終結(jié)果。因此，通過建立查找表的大整數(shù)相乘快速算法[13]可將原有的n次乘法運算降低至8次。

設(shè)存在一個m位和一個n位大整數(shù)A和B(m＞n＞1)，在做大整數(shù)取模運算時，

依照上述大整數(shù)乘法的分治思想，同樣構(gòu)造一個這樣的預(yù)處理表：首先將數(shù)字(1～9)與大整數(shù)B相乘運算的結(jié)果存入Value數(shù)組中，將結(jié)果的最高兩位存入aTable數(shù)組中，其中carry變量為進(jìn)位標(biāo)識，將第一個有乘法進(jìn)位的數(shù)存在aTable數(shù)組中的第一位，后面則依次存儲，這樣可以從小到大排列乘法結(jié)果最高兩位，由于數(shù)字(1～9)與任何一個大整數(shù)相乘前兩位一定不同，取存儲數(shù)組aTable中前兩位進(jìn)行比較，構(gòu)造一個預(yù)處理表sTable，其中sTable[x]中記錄著aTable數(shù)組中最高位為x(x∈Z且x∈[1,9])的數(shù)組標(biāo)識，并根據(jù)aTable數(shù)組前兩位從大到小記錄。這樣在試商過程中通過比較被除數(shù)最高兩位和預(yù)處理表sTable數(shù)組中的數(shù)，可直接從Value數(shù)組中找到試減的數(shù)，然后進(jìn)行減法運算得到新的被除數(shù)。接下來重復(fù)剛才的運算，直至最后被除數(shù)小于除數(shù)，這時的被除數(shù)就是最終的取模運算結(jié)果。

在每次試除運算中，通過改進(jìn)的預(yù)處理表可以直接找到試減的數(shù)，相對于不停地試商以找到試減的數(shù)，顯然效率更高。上面的方法在效率上將取模轉(zhuǎn)換成查表和減法，而構(gòu)造的預(yù)處理表在一次運算中可以重復(fù)利用，極大地提高了運算效率。

2.3 改進(jìn)算法的實現(xiàn)過程

改進(jìn)取模算法的原理基于十進(jìn)制運算，故為了能夠精確表示大整數(shù)，本文采用定長數(shù)組A[m]（數(shù)組初始化時為0）存儲大整數(shù)A，定長數(shù)組B[n]存儲大整數(shù)B，定長二維數(shù)組Value[9][n+1]來存儲數(shù)字(1～9)與大整數(shù)B的相乘運算的結(jié)果，二維數(shù)組aTable[9][2]存儲對應(yīng)的數(shù)字(1～9)和上面結(jié)果的前兩位，以加快構(gòu)建預(yù)處理表sTable[9][9]數(shù)組，此表類似一個矩陣，其中行標(biāo)識試商的數(shù)的最高位，列標(biāo)識準(zhǔn)確試商的標(biāo)志以便通過數(shù)組sTable直接在數(shù)組Value中找到要試減的數(shù)。

例如，大整數(shù)A為987 654 321 998 877 662 345，大整數(shù)B為56 321 987 213，在做大整數(shù)取模運算時，

首先，將數(shù)字1～9與大整數(shù)B相乘得到Value數(shù)組如表1所示。

表1 數(shù)組Value[9][12]

表1中第1行表示1與大整數(shù)B相乘的結(jié)果，第2行表示2與大整數(shù)B相乘的結(jié)果，以此類推，第9行表示9與大整數(shù)B相乘的結(jié)果。從表1中找到第一個比大整數(shù)B的位數(shù)大的數(shù)組行標(biāo)，即在第2行有第一個進(jìn)位，則進(jìn)位標(biāo)識carry為2。aTable數(shù)組存儲每行Value數(shù)組的高兩位，在建立aTable數(shù)組時，從Value[carrymod 9]開始記錄，這樣保證了aTable數(shù)組由小到大排序，如表2所示。

表2 數(shù)組aTable[9][2]

表2中第1行表示Value[2]的高兩位，第2行表示Value[3]的高兩位，以此類推，第9行表示Value[1]的高兩位。通過從后向前遍歷aTable數(shù)組建立預(yù)處理表sTable[9][9]（如表3），可以快速在Value數(shù)組中找到試減數(shù)，避免了每次試除時完全遍歷Value數(shù)組。檢測大整數(shù)B的位數(shù)為n，取大整數(shù)A的前n位按數(shù)組下標(biāo)從1到n賦給數(shù)組X[n+1]，可以發(fā)現(xiàn)：

（1）與數(shù)組X最高位相等的試減數(shù)可能有多個，這時必須從大到小逐個試減，若試減數(shù)比數(shù)組X大，則重新找比這一試減數(shù)小的數(shù)，進(jìn)行試減。

（2）在與數(shù)組X最高位相等的試減數(shù)中，都比數(shù)組X大，則必須找到比數(shù)組X最高位小1的最大試減數(shù)，進(jìn)行試減。

（3）在數(shù)組X最高位與所有試減數(shù)不等的情況下，這時必須找到比數(shù)組X最高位小且最接近的數(shù)組行標(biāo)，得到最大試減數(shù)進(jìn)行試減。

表3 數(shù)組sTable[9][9]

首先，在數(shù)組sTable的第i行(1≤i≤9)，從后向前遍歷aTable數(shù)組中第1列為i的數(shù)組行標(biāo)x(x∈Z且x∈[1,9])，經(jīng)過運算(x+carry-1)?mod?9后，依次將值存儲在此行（從大到小存儲試減數(shù)與數(shù)組X最高位相等時的數(shù)組行標(biāo)）；其次，從前向后遍歷aTable數(shù)組，得到第一個與i相等的數(shù)組行標(biāo)x′(x′∈Z且x′∈[1,9])，經(jīng)過運算(x′+carry-2)?mod?9后（若為0，則改為9），將值存儲在此行的下一列（在上一步存儲過程結(jié)束后的下一列，存儲試減數(shù)比數(shù)組X最高位小1的數(shù)組行標(biāo)）；最后，從前向后遍歷sTable數(shù)組中全為0的行，依次將其上一行的第一列的值賦予此行第1列，其余為0（在試減數(shù)與數(shù)組X最高位不相等的情況下，存儲比數(shù)組X最高位小且最接近的數(shù)組行標(biāo)）。建立好預(yù)處理表sTable數(shù)組后，在每次試除時，通過比較數(shù)組X的最高位和sTable數(shù)組行標(biāo)的關(guān)系，得到相應(yīng)的Value數(shù)組行標(biāo)，從而快速在Value數(shù)組中找到試減的數(shù)進(jìn)行減法運算。

表3中第1行表示，從后向前遍歷aTable數(shù)組中第1列為1的數(shù)組行標(biāo)，得x1=2和x2=1，運算后依次將3和2存儲在數(shù)組sTable的第1行第1列和第2列；然后，從前向后遍歷aTable數(shù)組，得到第一個與數(shù)組X的最高位相等的數(shù)組行標(biāo)x′=1，運算后將1存儲在數(shù)組sTable的第1行第3列，以此類推；最后，數(shù)組sTable的第6行全為0，則將第5行第1列的值存儲在第6行第1列，其余為0，以此類推，直到數(shù)組sTable的建立。若數(shù)組X最高位為1，則從sTable[1]這一行讀取數(shù)據(jù)，第一個是3，比較大整數(shù)A與Value[3]，若A大就減去Value[3]，否則就與Value[2]比較，若A大就減去Value[2]，否則減去Value[1]。算法步驟如下：

例子中，首先檢測B的位數(shù)為11，則取大整數(shù)A的前11位按數(shù)組下標(biāo)從1到11賦給數(shù)組X[12]，此時X的最高位為9，在sTable[9]讀取sTable[9][1]=1，則比較X與Value[1]，得X＞Value[1]，進(jìn)行減法運算X=X-Value[1]= 42 443 444 986，此時檢測X的位數(shù)，若為11，則擴(kuò)大10倍再加上大整數(shù)A的第12位變成424 434 449 868，在上述數(shù)組X中，將大整數(shù)A的第12位添加至X數(shù)組下標(biāo)的第11位即可（若位數(shù)為10，則擴(kuò)大10倍加上大整數(shù)A的第12位后再擴(kuò)大10倍加上大整數(shù)A的第13位，在上述數(shù)組X中，將大整數(shù)A的第12位和第13位依次添加至X數(shù)組下標(biāo)的第10位和第11位即可）。此時X最高位為4，在sTable[4]讀取sTable[4][1]=8，則比較X與Value[8]，得X＜Value[8]，條件失效不進(jìn)行減法運算，在sTable[4]讀取下一個sTable[4][2]=7，則比較X與Value[7]，得X＞Value[7]，進(jìn)行減法運算X=X-Value[7]= 30 180 539 377，X的位數(shù)為11，擴(kuò)大10倍加上大整數(shù)A的第13位，X=301 805 393 778。以此類推，直到大整數(shù)A中所有數(shù)字都參與完運算，程序結(jié)束得到最終取模結(jié)果為52 870 988 247。

以上的例子中，在建立sTable表后，最多查找3次必然可以找到試減數(shù)進(jìn)行試減；若沒有此表，最多查找9次才可以找到試減數(shù)進(jìn)行試減。查找和比較次數(shù)都大大減少，故sTable表的建立提升了算法效率。

改進(jìn)的算法進(jìn)行運算時，需要遍歷m-n次，每次遍歷做O(1)次比較和一次n位減法，得到預(yù)處理表時需要8次乘法，以減法運算作為基本運算，乘法時間復(fù)雜度為O(1)，可忽略不計，故此算法的時間復(fù)雜度為O(n(m-n))，空間復(fù)雜度為O(n)。

3 算法效率分析與比較

本文采用Java[14]語言實現(xiàn)了改進(jìn)的大整數(shù)取模算法，實驗計算機(jī)配置如下：操作系統(tǒng)為Windows 7，CPU為酷睿i3-2330M，2 GB的DDR3內(nèi)存。

改進(jìn)的算法核心部分是建立預(yù)處理表，而得到此矩陣只需要進(jìn)行8次數(shù)字2～9與大整數(shù)乘法運算，利用預(yù)處理表就直接找到試商結(jié)果。相對文獻(xiàn)[7]中提出的算法，本文算法在乘法效率上優(yōu)于前者，與文獻(xiàn)[7]得出的性能表相比，體現(xiàn)了改進(jìn)算法的優(yōu)越性。故普通取模算法采用基于R進(jìn)制模余數(shù)表的快速動態(tài)取模算法[15]，在和改進(jìn)的取模算法進(jìn)行比較之后，每種位數(shù)使用10組不同的大整數(shù)進(jìn)行實驗，得到程序整體運行的平均時間實驗數(shù)據(jù)表如表4所示。

表4 算法運行位數(shù)-時間表

表4顯示普通算法和改進(jìn)算法的運行時間隨位數(shù)變化的數(shù)據(jù)，可以看出隨著位數(shù)的不斷增大，普通算法的運行時間增長很快，從100位時的0.009 0 s增長到3 000位時的11.468 3 s，而改進(jìn)后算法的運行時間增長緩慢，從100位時的0.000 9 s增長到3 000位時的0.021 9 s，充分說明改進(jìn)后的算法效率提升得很明顯。

圖1和圖2分別表示普通算法和改進(jìn)算法的運行時間隨位數(shù)變化的趨勢，可以看出隨著位數(shù)的不斷增大，普通算法的運行時間是以109ns級的速度增長，原因是隨著位數(shù)的增大，在每次試除時要進(jìn)行多次因式分解，使得算法的開銷增大，當(dāng)位數(shù)增長到3 000位時，算法的效率已經(jīng)無法容忍；改進(jìn)的大整數(shù)取模算法運行時間是以107ns級的速度增長，通過訪問查詢矩陣得到試商結(jié)果，減少大量的算法開銷，即使位數(shù)增長到3 000位時，算法的效率也很高。顯然，在對大整數(shù)的取模運算中，通過實驗數(shù)據(jù)證明了根據(jù)分治法思想提出的大整數(shù)取?？焖偎惴ǖ暮侠硇院透咝?。

圖1 普通算法的位數(shù)-時間圖

圖2 改進(jìn)算法的位數(shù)-時間圖

4 結(jié)束語

通過對大整數(shù)取模運算的理論研究和實驗分析，本文采用分治法的思想，建立預(yù)處理表，有效地將時間復(fù)雜度降為O(n(m-n))。研究結(jié)果和程序?qū)嶒灁?shù)據(jù)表明了改進(jìn)算法在大數(shù)取模運算時的高效性和合理性，并隨著n的不斷增大，效率提升越明顯。但在大整數(shù)取模運算中，由于大數(shù)比較和減法是傳統(tǒng)的按位運算，使得改進(jìn)算法整體效率有所降低，將在以后的研究中采用滑動窗口方式提高大數(shù)比較和減法效率。綜上所述，本文以空間換取時間，采用分治法策略，提高了大整數(shù)取模運算在實際應(yīng)用中的效率，對公鑰密碼學(xué)算法的研究具有重要意義。

[1]Rivist R，Shamir A，Adleman L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM，1978，21（2）：120-126.

[2]Diffie W，Hellman M E.New direction in cryptography[J]. IEEE Transactions on Information Theory，1976，22（6）：644-654.

[3]Montgomery P L.Modular multiplication without trial division[J].Mathematics of Computation，1985，44（170）：519-521.

[4]陳恭亮.信息安全數(shù)學(xué)基礎(chǔ)[M].北京：清華大學(xué)出版社，2004：1-29.

[5]王曉東.計算機(jī)算法設(shè)計與分析[M].2版.北京：清華大學(xué)出版社，2008：19-30.

[6]Chen Junhong，Wu Hao-Hsuan，Lin Wen-Ching，et al.A new modular exponentiation architecture for efficient design of RSA cryptosystem[J].IEEE Transactions on Information Theory，2008，16（9）：1151-1161.

[7]王巖，周亮，王遠(yuǎn)奎，等.大整數(shù)模運算的軟件實現(xiàn)方案[J].信息安全與通信保密，2005，26（2）：150-151.

[8]Ko? C K，Kaliski B S.Analyzing and comparing montgomery multiplication algorithms[J].IEEE Micro，1996，16（3）：26-33.

[9]趙學(xué)秘，陸洪毅，戴葵，等.一種高性能大數(shù)模冪協(xié)處理器SEA[J].計算機(jī)研究與發(fā)展，2005，42（6）：924-929.

[10]劉強(qiáng)，佟冬，程旭.一款RSA模乘冪運算器的設(shè)計與實現(xiàn)[J].電子學(xué)報，2005，33（5）：923-927.

[11]王遠(yuǎn)奎.大整數(shù)快速模運算算法與實現(xiàn)研究[D].成都：電子科技大學(xué)，2003.

[12]童元滿.高性能公鑰密碼協(xié)處理器的設(shè)計與實現(xiàn)[D].長沙：國防科學(xué)技術(shù)大學(xué)，2004.

[13]周健，李順東，薛丹.改進(jìn)的大整數(shù)相乘快速算法[J].計算機(jī)工程，2012，38（16）：121-123.

[14]Eckel B.Java編程思想[M].陳昊鵬，譯.4版.北京：機(jī)械工業(yè)出版社，2007：209-300.

[15]章昭輝，王曉蒲，霍劍青.公鑰密碼體制中快速模算法的研究[J].計算機(jī)工程與應(yīng)用，2002，38（8）：56-58.

XU Xin,LI Shundong

School of Computer Science,Shaanxi Normal University,Xi’an 710062,China

Modular operation is a basic operation in modern cryptography.It plays an important role in public key cryptography based on factorization assumption.This paper proposes a fast modular operation algorithm for them-bit andn-bit integers.This algorithm,utilizing divide and conquer thought,transfers modular operation into subtractions,and then establishes a preprocessing table to further reduce the computational complexity toO(n(m-n)).Experiments show that this algorithm outperforms existing algorithms.

modular operation;cryptography;preprocessing table;divide and conquer;computational complexity

大整數(shù)取模運算是密碼學(xué)應(yīng)用的一種基本運算，尤其是在基于因子分解假設(shè)的公鑰密碼學(xué)中占有極其重要的地位。提出的m位和n位兩個大整數(shù)快速取模算法，是利用分治法思想，將n位的大整數(shù)分解為n個獨立十進(jìn)制整數(shù)的組合，通過八次大整數(shù)乘法建立一個預(yù)處理表，能夠有效地將大整數(shù)取模的計算復(fù)雜度降為O(n(m-n))，經(jīng)大量實驗數(shù)據(jù)驗證該算法的合理性和高效性。

大整數(shù)取模；密碼學(xué)；預(yù)處理表；分治法；計算復(fù)雜度

A

TP301

10.3778/j.issn.1002-8331.1212-0149

XU Xin,LI Shundong.Fast algorithm for modular operation.Computer Engineering and Applications,2014,50（22）：136-140.

國家自然科學(xué)基金（No.61070189，No.61272435）。

許鑫，男，碩士研究生，主要研究方向：信息安全，密碼學(xué)。E-mail：xuxinshr@vip.qq.com

2012-12-13

2013-03-11

1002-8331（2014）22-0136-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-29，http://www.cnki.net/kcms/detail/11.2127.TP.20130329.1540.009.html

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎