基于Ｋｎｕｔｈ與Ｋａｒａｔｓｕｂａ乘法的大整數(shù)乘法研究

韓　猛　方賢進(jìn)　郭玉秀　李　濤

（安徽理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮南232001）

摘要： 在RSA、DiffieHellman密碼系統(tǒng)的算法中都要用到大整數(shù)乘法算術(shù)。介紹了Knu th經(jīng)典乘法、Karatsuba乘法以及它們的計(jì)算時(shí)間復(fù)雜性，在此基礎(chǔ)上提出了一個(gè)新的大整 數(shù)乘法技巧，并且在理論上和實(shí)踐上被證明是有效的。實(shí)驗(yàn)結(jié)果也顯示改進(jìn)的大整數(shù)乘法算 法在實(shí)現(xiàn)大整數(shù)乘法運(yùn)算時(shí)具有更高的效率。

關(guān)鍵詞：Knuth乘法；Karatsuba乘法；大整數(shù)乘法；分治法

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí) 碼：A[WT]文章編號(hào)：16721098(2008)02006703

Research on Large Integer Multiplication Based on Knuth and

Karatsuba Multiplication

HAN Meng,FANG Xianjin,GUO Yuxiu,LI Tao

(School of Computer Science and Engineering,Anhui University of Science and Tec hnology,Huainan Anhui 232001,China) Abstract:Algorithms in cryptosystem such as RSA and DiffieHellman require larg e integer multiplication. In the paper Knuth classical multiplication, Karatsubamultiplication and their time complexity were presented, on the basis of whicha new large integer multiplication trick was put forward and proved available intheory and practice. The experiment showed that the improved multiplication alg orithm is more efficient in implementation of large integer multiplication.

Key words:Knuth multiplication；Karatsuba multiplication；large integer multipl ication；divide and conquer

對(duì)大多數(shù)的數(shù)論問(wèn)題并且包括象RSA、ECC等公鑰密碼系統(tǒng)的算法中，大整數(shù)乘法是其中的基 本操作。 關(guān)于大整數(shù)乘法算術(shù)的文獻(xiàn)有很多， 例如有Karatsuba乘法、 Toom乘法，快速傅 立 葉變換技巧，Sch﹐[DD(-*2/3]..nhageStrassen技巧，經(jīng)典的Knuth 乘法等［17］。

大多數(shù)乘法運(yùn)算的技巧都是利用“分治法”工具：將一個(gè)大的乘法問(wèn)題減小為一組較小的乘 法問(wèn)題，但是一直用同一個(gè)單一的方法進(jìn)行遞歸到小問(wèn)題的做法被認(rèn)為是一個(gè)錯(cuò)誤的選擇。 因?yàn)椋孩?雖然有很多乘法運(yùn)算的技巧，但是沒(méi)有一種技巧適用于所有的情況， 在操作數(shù)長(zhǎng) 度不同的情況下， 不同的乘法技巧所產(chǎn)生的效率是不一樣的， 所以應(yīng)根據(jù)乘法運(yùn)算中的 操 作數(shù)長(zhǎng)度的不同選擇不同的算法； ② 通常情況下，最佳的乘法運(yùn)算算法應(yīng)能在遞歸的不同 層次使用不同的方法。

文章的主要目標(biāo)是對(duì)Karatsuba算法進(jìn)行改進(jìn)，試圖找出這樣一個(gè)條件并加以證明，當(dāng)滿足 這個(gè)條件時(shí)基于分治法的Karatsuba乘法被反復(fù)遞歸地調(diào)用，當(dāng)不滿足這個(gè)條件時(shí)，使用經(jīng) 典的Knuth乘法進(jìn)行運(yùn)算。

1標(biāo)記

文中所有的大整數(shù)都以玝進(jìn)制表示， 基本的算術(shù)運(yùn)算包括兩個(gè)以b進(jìn)制表示的單精度整 數(shù)的加、 減、 乘、 除。 用玝進(jìn)制表示一個(gè)正整數(shù)玴通常寫成 玴=(u1u2…un)，其中的單精度整數(shù)ui (1≤i≤n)稱為數(shù)字，并且0≤ui≤b-1 。例如，如果玝=232=0x100000000，那么0≤玼i≤0xffffffff(1≤i≤n )，則整數(shù)(ffffffffffffffff)b有兩位數(shù)字。

2經(jīng)典的Knuth乘法及計(jì)算時(shí)間

若玴,q是b進(jìn)制表示的非負(fù)整數(shù)，玴=(u1u2…un)b, q=(v1v2…vm)b，它們的乘積w可表示成w=p?q=(w1w2…w﹎+n)b，用經(jīng)典Knuth乘法［8］ 計(jì)算玾的算法可表示如下

step1：玾1,w2,…,w﹎+n←0,j←m;

4對(duì)大整數(shù)乘法的改進(jìn)

優(yōu)化大整數(shù)乘法的方法是，首先利用分治法遞歸地調(diào)用Karatsuba乘法去減小乘法的規(guī)模， 當(dāng)乘數(shù)的長(zhǎng)度達(dá)到某一個(gè)級(jí)別時(shí)，使用經(jīng)典的Knuth乘法進(jìn)行剩下的乘法運(yùn)算。

定理1存在這樣的玭，使得經(jīng)典的Knuth乘法的計(jì)算時(shí)間 小于Karatsuba乘法。

證明：設(shè)玊1(n)，T2(n)分別表示經(jīng)典的Knuth乘法和Karatsuba乘法的計(jì)算時(shí)間，根 據(jù)前面的分析可以得到

T1(n)=n T2(n)=9?n玪og23-10n

肯定存在這樣的n滿足T1(n)≤T2(n)，也就是n2≤9?n玪og23-10n ＜9?n

也就是說(shuō)當(dāng)玭<256時(shí)，經(jīng)典的Knuth乘法的效率要高于Karatsuba乘法。

定理2根據(jù)以下策略大整數(shù)乘法的效率是最高的：如果玭> 16(n=2琸)，遞歸地調(diào)用Karatsuba乘法，當(dāng)玭=16時(shí)遞歸調(diào)用返回（遞歸出口）， 調(diào)用經(jīng)典的Knuth乘法計(jì)算兩個(gè)較小整數(shù)的乘積。

證明：設(shè)玊(n)表示Karatsuba乘法的計(jì)算時(shí)間，假設(shè)如果玭>m時(shí)Karatsuba乘法被遞 歸地調(diào)用，否則經(jīng)典的Knuth乘法被調(diào)用。因此有

T(n)=[JB(｛]m n=m3T(n/2)+5n,n＞m[JB)]Иチ瞠玭=2琸,h(k)=T(n)=T(2琸) ，那么T(n)能寫成如下形式

h(k)=3h(k-1)+5?2琸=3(3h(k-2)+5?2琸-1)+5?2琸=…=3琸-ih(i)+ 5?3琸-(i-1)?2琲-1+…+5.30?2琸

令 玬=2琲

h(k)=[SX(]4琲+10?2琲[]3琲[SX)]?n玪og23-10n

再令f(i)=[SX(]4琲+10?2琲[]3琲[SX)], 函數(shù)f(i) 有最小值，當(dāng)i=[JB(［][S X(]玪og2(10log2[SX(]2[]3[SX)])-log2(log2[SX(]4[]3[SX)])[]log22-log2 3[SX)]玔JB)］]=4時(shí)，也就是當(dāng)i=4時(shí)，m=2琲=16，T(n)ё钚。最小值為

T┆玬in(n)=[SX(]416[]81[SX)]n玪og23-10n=O(n玪og23 )

5實(shí)驗(yàn)結(jié)果和結(jié)論

目前大多數(shù)計(jì)算機(jī)的字長(zhǎng)是32并且大多數(shù)C語(yǔ)言的編譯器都支持對(duì)INTEL MASM指令的調(diào)用， 因此本文中一個(gè)單精度整數(shù)是用232進(jìn)制表示的。 如果想要計(jì)算兩個(gè)32 bit正整數(shù)的乘積， 可以調(diào)用下列的匯編代碼， 以加快運(yùn)算速率， 這些代碼可以被認(rèn)為 是一個(gè)基本操作，其時(shí)間復(fù)雜度為O(1)［10］。

//Computes 玴 = (p1p0) = 玿 * 珁.…

--asm{

mov eax, 玿

xor edx, edx

mul珁

; Product in edx:eax

mov ebx, 玴

mov dword ptr ［ebx］, eax

mov dword ptr ［ebx+4］, edx

}

將經(jīng)典的Knuth乘法、Karatsuba乘法以及改進(jìn)的大整數(shù)乘法的計(jì)算時(shí)間進(jìn)行比較(見(jiàn)表1)， 其中Digits是以232進(jìn)制表示的乘數(shù)的長(zhǎng)度，測(cè)試環(huán)境是AMD Athlon CPU 1.1GHz, 25 6M RAM, Windows XP OS, MS Visual C++ 6.0編譯器。

表1三種乘法的計(jì)算時(shí)間比較s

Digits(232進(jìn)制)[]Knuth[]Karatsuba[]改進(jìn)的乘法2560.030.030.015120.040.110.011 0240.170.3810.052 0480.7210.9610.134 0962.7342.8740.3818 19210.9668.3221.141

表1顯示Karatsuba乘法的效率在實(shí)際中比經(jīng)典的Knuth乘法要低，這與理論上是不一致的， 原因是Karatsuba乘法涉及到大量的遞歸調(diào)用，在此過(guò)程中要花費(fèi)大量的時(shí)間進(jìn)行內(nèi)存的請(qǐng) 求與釋放。改進(jìn)的乘法利用了Karatsuba乘法和經(jīng)典的Knuth乘法的優(yōu)點(diǎn)：如果用232 進(jìn)制表示的乘數(shù)的長(zhǎng)度大于16時(shí)，Karatsuba乘法被不斷地遞歸調(diào)用，而當(dāng)長(zhǎng)度是16時(shí)經(jīng)典 的Knuth乘法被調(diào)用用于計(jì)算兩個(gè)較小整數(shù)的乘積。從表1也可看出，改進(jìn)的大整數(shù)乘法算法 比Knuth乘法和Karatsuba乘法明顯地減少了計(jì)算時(shí)間。

參考文獻(xiàn)：

［1］R L RIVEST, A SHAMIR, L ADLEMAN. A Method for Obtaining Digit al Signatures and PublicKey Cryptosystems［J］.Communications of the ACM,1978 .21(2) ：120126.

［2］MICHAEL ROSING.Implementing Elliptic Curve Cr yptography［M］. Greenwich: Manning Publications Co,1999：314320.

［3］ANATOLY A,KARATSUBA,Y OFMAN.Multiplication of Multidigi t Numbers on Automata［J］.Soviet Physics Doklady,1963：595596.

［4］DAN ZURAS.On Squaring and Multiplying Large Integers［M］. AR ITH-11: IEEE Symposium on Computer Arithmetic, 1993：260271.

［5］E ORAN BRIGHAM.The fast Fourier Transform and its Applicati ons［M］. New Jersey :Prentice-Hall, Englewood Cliffs, 1988：232242.

［6］A SCH㎡[DD(-*1/3]..NHAGE,V STRASSEN.Sch nelle Multiplikation Groβer Zahlen［J］.Computing 7, 1971:281292.

［7］DONALD E KNUTH.The Art of Computer Programming,Vol 2 Seminume rical Algorithms［M］.second edition. Massachusetts: Addison-Wesley,1981：7537 61.

［8］A MENEZES,P VAN,OORSCHOT.Handbook of AppliedCryptography［M］.CRC Press Inc., 1996：347351. ［9］TOM ST DENIS.BigNum Math Implementing Cryptographic MultiplePrecision Arithmetic［M］.SYNGRESS Publishing,2003：116126.

［10］THOMAS H CORMEN,CHARLES E LEISERSON,RONALD L. Rivest, Cli fford St ein, 算法導(dǎo)論［M］.第2版.潘金貴,顧鐵成,李成法,等譯. Massachusetts: The MIT Pr ess, 2001：652658.

(責(zé)任編輯：李麗)