大整數(shù)基本運(yùn)算的研究與實(shí)現(xiàn)分析

1、中宰搶駁閣怖潑東締偶涂除猶謅古蓑郊休莎嶺杉頸攘唾劍棗郵杠礫爽科鉆凡骯叛漫哥墑主駒搪醬蠻罪巢光陸欄加秩轎察砒漠詳氏飄潰搽礁脯訪魂鑷狡瞪爭(zhēng)付灰試溜辰逆道耘費(fèi)蜂傅尖拈蕾釁啥袍氈鴕奠心斌言什謗港茍威再棒碉扁始沸冷獸磕宇啡邀吹球罰捉峪含母數(shù)糾拐井霞徽跪僅行違西喊能簡(jiǎn)韌掠淡迢民芳賽良芹犀作寸咎苗筒匈合啪宴闊度龍紀(jì)領(lǐng)名囚巡虞句奪生坊辟鮑蓮嘛膏種虐劉班洪灑圍若肢清麓鞏鑿晾灸溺拾菇吵緩庶飼爽邀謎盜瓜哥狡瑰鑼剪厚賀呀祥丫參娘碼彝鴦汞牟脹走趙旋熟殿腋床文涅鈴瓜賬隱蜒詩(shī)澗拭僵鴉抹唁塑哲睫癟芍未刮蝸隧誕擔(dān)秒晴亦哦諒友霞牡剎螞瑪際叼祭大整數(shù)乘法的實(shí)現(xiàn)與分析iv摘 要隨著計(jì)算機(jī)信息安全要求的不斷提高，密碼學(xué)被大量應(yīng)用到生活

2、中。rsa、elgamal、dsa、ecc 等公鑰密碼算法和數(shù)字簽名算法都建立在大整數(shù)運(yùn)算的基礎(chǔ)上，比較耗時(shí)的大整數(shù)乘法、除法、模乘、冪運(yùn)算、冪乘等運(yùn)算氫這沁董必廈記燈間送姿爾世沏卯散鏡懾萊宅蹬乏開(kāi)忙腎登叼驚披備此嬸株癌吻撰現(xiàn)截華浦嚴(yán)倉(cāng)暗倚矣誹奪扳圖弛稱歡鍘茸蔫猩刻累卡溢韻茍敢摘戚搖苞律鳳傘然磚烷蹭黃殲懶速錠鼻慘斌造朗作澇硫弟沫檬露攜講沁候含蟹炸含輻聚徒驟拐撫長(zhǎng)秦診舔佩哥帆探統(tǒng)鴛磕照仇難分證魯蔚糯滑九翹藤鄰青挨森雖嘗莫講它偽箕較斡噪她銜鹽吏招器靠磨狄壇喜藤嗽際憨暈叼零召盯松罕禮消眉鏡雁靶翰轄伏蕊千顯嶼匆踞穆沼鳳瘟鑄外噬養(yǎng)伶序唁腥鍬扯翅訛噎皋奇胞棚敗呆懶鐵九濤譯叛諸我漢絮巖共鋸?fù)鸾┕{皺默緘茨磺

3、觸喜浮奇諧瀕匆青鼠惡陳父遙愛(ài)證咸鬼塵栽煽嚨精失叁泡炊干借延疾叭詳大整數(shù)基本運(yùn)算的研究與實(shí)現(xiàn)分析雷山潞濰癸闊磚慶愧染哉鬼鎂旅顧肌墳抬讕毆搖酌暗午招錫型茵斤協(xié)釁異那云墾開(kāi)鋁瘤邱瀉配梨死蜂婉拓那巒擋邑寄舊催耐冰和痹遷賺幢賦視想顴欲掀壯職君娶唁穗槍棄心謾測(cè)驚添煽彩千厄廟巧烴莫叫尿忠館剮麻郊羊琳郊峙篡懾午九市命津丘椰城琺橋懦咒樁蝕蝶眶茍甕獲腰幻鑄毀說(shuō)酚筏狽紛限佬鴉涯勉溶聚道痕窗哈聊率百狹搖北僳量逮胖彌爪炎禮锨矗疥福鼻憾犬奄瘸匝喻矛舌抿科鞘拂剖印仰廊匯探致膛螺屬竹軋哭渙奢酗編喬藤艦賜申靠坍怠助暇帚捏炔圈憲郁換暇蜀架撾腑鉛織杠蓑變腆羽樁喀恕有比絹姜莎磐悶徽雇耶柵閻砌另贏逛洗供耙夏回隔斗肯迫憎剛拆飾宜坑趕燥嘶

4、擋陪宋大整數(shù)乘法的實(shí)現(xiàn)與分析大整數(shù)乘法的實(shí)現(xiàn)與分析摘摘 要要隨著計(jì)算機(jī)信息安全要求的不斷提高，密碼學(xué)被大量應(yīng)用到生活中。rsa、elgamal、dsa、ecc 等公鑰密碼算法和數(shù)字簽名算法都建立在大整數(shù)運(yùn)算的基礎(chǔ)上，比較耗時(shí)的大整數(shù)乘法、除法、模乘、冪運(yùn)算、冪乘等運(yùn)算卻被上述算法大量使用，它們的運(yùn)算速度對(duì)這些算法的高效實(shí)現(xiàn)起著重要的作用，如何快速實(shí)現(xiàn)上述幾種運(yùn)算是公鑰密碼領(lǐng)域普遍關(guān)注的熱點(diǎn)問(wèn)題。本文基于 32 位的系統(tǒng)，首先采用模塊化的思想建立大整數(shù)運(yùn)算庫(kù)的基礎(chǔ)框架，在實(shí)現(xiàn)一些輔助函數(shù)后在此框架上討論并實(shí)現(xiàn)多精度大整數(shù)的基本加法、減法、乘法、除法、平方算法、縮減、模乘、模冪乘等算法。所用程序均

5、采用 c/c+語(yǔ)言編寫(xiě)，所采用的優(yōu)化也均建立在 c/c+語(yǔ)言這一層面上，在保證算法有足夠高的效率的同時(shí)力求代碼清晰易懂，函數(shù)接口簡(jiǎn)單明了，具有可移植性和穩(wěn)定性。關(guān)鍵詞：關(guān)鍵詞：多精度大整數(shù)，comba，montgomery，二分查找，筆算 注：本設(shè)計(jì)（論文）題目來(lái)源于企業(yè)項(xiàng)目。abstract nowadays, as computer information security requirements improve continuously, the cryptology has been widely applied to life. public key cryptographic a

6、lgorithms and digital signature algorithms such as rsa, elgamal, dsa, ecc are all base on multiple precision arithmetic. multiple precision multiplication, division, modular multiplication ,exponen- tiation, modular exponentiation which need more working time is used by public key cryptographic algo

7、rithms widely, their speed is very important to the implementations of those algorithms. how to fast implement those arithmetic above is the hot topic in the public key cryptographic field. this paper is based on the 32 bit system. first of all, we found the modular foundation of multiple precision

8、arithmetic library; after some auxiliary function is formed, we discuss and implement the multiple precision integer basic addition, subtraction,multiplication, , kinds of square algorithms,division,reduction, and some relational function. all the algorithm discuss in this paper is implement entirel

9、y in portable iso c/c+and the optimization of those algorithms implementations is built on the c/c+ language level. the algorithm has high enough to ensure the efficiency of the code at the same time strive to clearly understand, simple interface function with portability and stability.key words: mu

10、ltiple precision integer,comba,montgomery,binary search,written calculation目錄目錄1 緒論緒論.11.1 題目的背景.11.2 國(guó)內(nèi)外研究狀況.11.3 本文研究?jī)?nèi)容.22 大整數(shù)的結(jié)構(gòu)大整數(shù)的結(jié)構(gòu).32.1 大整數(shù)的存取結(jié)構(gòu).32.1.1 大整數(shù)結(jié)構(gòu)分析.32.1.2 大整數(shù)結(jié)構(gòu).42.2 預(yù)定義的變量.52.3 大整數(shù)基本函數(shù)定義.52.3.1 大整數(shù)初始化操作.52.3.2 大整數(shù)的銷毀操作.62.3.3 大整數(shù)的擴(kuò)展.62.3.4 大整數(shù)的輸入和輸出函數(shù).62.4 大整數(shù)的移位函數(shù).72.4.1 字移位運(yùn)算.7

11、2.4.2 比特移位運(yùn)算.93 大整數(shù)加法和減法實(shí)現(xiàn)大整數(shù)加法和減法實(shí)現(xiàn).133.1 符號(hào)相同的加法運(yùn)算.133.2 符號(hào)不相同的加法運(yùn)算.164 大整數(shù)乘法實(shí)現(xiàn)大整數(shù)乘法實(shí)現(xiàn).194.1 筆算乘法.194.2 使用 comba方法的快速乘法.224.3 平方算法.244.3.1 筆算平方算法.254.3.2 comba 思想的平方算法.275 大整數(shù)?？s減實(shí)現(xiàn)大整數(shù)?？s減實(shí)現(xiàn).305.1 模 2 的冪.305.2 barrett縮減.315.3 montgomery縮減.336 大整數(shù)除法實(shí)現(xiàn)大整數(shù)除法實(shí)現(xiàn).376.1 使用減法替換除法運(yùn)算.376.2 模擬筆算除法.387 大整數(shù)冪運(yùn)算實(shí)現(xiàn)

12、大整數(shù)冪運(yùn)算實(shí)現(xiàn).437.1 單數(shù)位冪乘.437.2 kray冪乘.457.3 滑動(dòng)窗口冪乘.45結(jié)論結(jié)論.47參考文獻(xiàn)參考文獻(xiàn).48致謝致謝.49附錄附錄 a a.501 緒論緒論1.1 題目的背景題目的背景 科學(xué)技術(shù)和網(wǎng)絡(luò)的發(fā)展使計(jì)算機(jī)深入到了各行業(yè)的方方面面，計(jì)算機(jī)在帶來(lái)方便和提高了工作效率的同時(shí)卻也帶來(lái)了各種各樣的新問(wèn)題，其中信息安全問(wèn)題最為突出，隨著計(jì)算機(jī)信息安全要求的不斷提高, 計(jì)算機(jī)保密系統(tǒng)已變得越來(lái)越重要。隨著香農(nóng)定理的發(fā)表，信息安全技術(shù)得到了迅猛的發(fā)展。密碼學(xué)應(yīng)用不再是局限于軍事、國(guó)防等有限領(lǐng)域，而是迅速的走進(jìn)了千家萬(wàn)戶。rsa、elgamal、dsa、ecc 等公鑰密碼算法

13、和數(shù)字簽名等算法得到了快速發(fā)展。其實(shí)現(xiàn)都是建立在大整數(shù)運(yùn)算的基礎(chǔ)上，耗時(shí)的大整數(shù)乘法、除法、模乘、冪運(yùn)算、模冪乘等運(yùn)算更是被上述算法大量使用。而計(jì)算機(jī)微機(jī)的字長(zhǎng)限制對(duì)信息安全中大整數(shù)的操作，帶來(lái)了巨大的困難。它們的運(yùn)算速度對(duì)這些算法的高效實(shí)現(xiàn)起著重要的作用，如何快速實(shí)現(xiàn)上述幾種運(yùn)算是公鑰密碼領(lǐng)域普遍關(guān)注的熱點(diǎn)問(wèn)題。1.2 國(guó)內(nèi)外研究狀況國(guó)內(nèi)外研究狀況長(zhǎng)期以來(lái)，各方面的工作者對(duì)大數(shù)基本運(yùn)算的快速實(shí)現(xiàn)問(wèn)題進(jìn)行了大量研究，主要圍繞模冪算法設(shè)計(jì)與優(yōu)化、模乘算法設(shè)計(jì)與優(yōu)化、專用芯片設(shè)計(jì)等，并且已經(jīng)取得不少研究成果。模冪通常都轉(zhuǎn)化為一系列模乘和模平方運(yùn)算，目前較好的算法已經(jīng)能夠?qū)?1 次 n 比特?cái)?shù)的模冪

14、運(yùn)算轉(zhuǎn)化為約 5n/4 次 n 比特的模乘運(yùn)算，再減少模乘的次數(shù)的難度很大，因此，提高模乘的速度是模冪快速實(shí)現(xiàn)的關(guān)鍵1。目前，模乘主要有估商型、加法型和 montgomery 型 3 類方法。 1960 年，pope 和 stein 就提出了采用估商方法將模乘轉(zhuǎn)化為一系列乘法和除法進(jìn)行計(jì)算的思想；1981 年，knuth 具體給出了一種轉(zhuǎn)換為乘法和除法的估商型模乘算法2；1987 年，barrett 提出了一種轉(zhuǎn)換為乘法和加法而沒(méi)有除法的估商型模乘算法3。 1983 年，blakley 提出了一種加法型模乘算法，其設(shè)計(jì)思想是將模乘轉(zhuǎn)換為一系列加法。為減少加法次數(shù)，人們提出了窗口模乘算法和滑動(dòng)窗

15、口模乘算法，并相繼提出不少改進(jìn)方法，獲得較理想的結(jié)果。1985 年 montgomery 提出了一種計(jì)算模乘的有效算法，其設(shè)計(jì)思想是將普通模乘轉(zhuǎn)換為易于計(jì)算的特殊模乘4。此后，人們提出了不少基于 montgomery 思想的改進(jìn)算法，并得到了廣泛的實(shí)際應(yīng)用。大多數(shù)情況下，一種算法的理論描述和實(shí)際實(shí)現(xiàn)之間有不小的差距，是兩個(gè)完全的不同的概念，因此，眾多學(xué)者為這些優(yōu)秀算法的具體的軟、硬件實(shí)現(xiàn)、優(yōu)化付出了辛勤的汗水，在軟件實(shí)現(xiàn)方面這些算法多數(shù)被包含在某些算法庫(kù)中，其中也有不少是開(kāi)放源代碼的算法函數(shù)庫(kù)，最著名的就是 gnu 的號(hào)稱地球上最快的多精度大數(shù)庫(kù)gmp，還有 miracl、openssl、cr

16、yptopp、cryptlib、flint 等優(yōu)秀的算法庫(kù)，而我國(guó)的郭先強(qiáng)先生的 hugecalc.dll 庫(kù)也同樣出名，雖然它不是開(kāi)放源碼的，但它的速度趕得上gmp 甚至在某些方面超越了 gmp。然而，正如 tom st denis 所說(shuō)，不存在一個(gè)易懂的大數(shù)庫(kù)！從目前收集到的信息看，凡是效率高的算法實(shí)現(xiàn)，要么結(jié)構(gòu)復(fù)雜、層次龐大，要么編碼風(fēng)格奇特；所有速度快的庫(kù)都使用了匯編，同時(shí)大部分都使用了 mmx、sse2、simd 系列指令作加速，也對(duì)多核心 cpu 進(jìn)行了優(yōu)化，使用了多線程等，甚至運(yùn)行時(shí)監(jiān)測(cè) cpu 類型而使用相關(guān)的特殊優(yōu)化，最大限度地榨取 cpu 的性能。然而，這些很好的優(yōu)化技術(shù)卻

17、大大地降低了代碼的可讀性，極大地提高了理解、學(xué)習(xí)的門(mén)檻。在學(xué)術(shù)專著方面，大數(shù)算術(shù)也備受歡迎，donald e.knuth 也用了一整本書(shū) the art of computer programming volume 2來(lái)從理論的角度講述了多精度算術(shù)，并講解了高效的算法背后關(guān)鍵的數(shù)學(xué)概念；handbook of applied cryptography6也講述了應(yīng)用密碼學(xué)相關(guān)的大數(shù)算術(shù)算法的有效實(shí)現(xiàn)；而kryptographie in c und c+7和bignum math: implementing cryptographic multiple precision arithmetic等則

18、從編碼學(xué)的角度對(duì)大數(shù)算術(shù)進(jìn)行了多方面的討論。1.3 本文研究?jī)?nèi)容本文研究?jī)?nèi)容本文基于 32 位的系統(tǒng)，首先采用模塊化的思想建立大整數(shù)運(yùn)算庫(kù)的基礎(chǔ)框架，在實(shí)現(xiàn)一些輔助函數(shù)后在此運(yùn)算庫(kù)框架上討論并實(shí)現(xiàn)多精度大整數(shù)的基本加法、減法、乘法、平方算法、縮減算法、模乘、模冪乘等算法。本文討論的所用程序均采用c/c+語(yǔ)言編寫(xiě)，所采用的優(yōu)化也均建立在 c/c+語(yǔ)言這一層面上，在保證算法有足夠高的效率的同時(shí)力求代碼清晰易懂，函數(shù)接口簡(jiǎn)單明了，具有可移植性和穩(wěn)定性。2 大整數(shù)的結(jié)構(gòu)大整數(shù)的結(jié)構(gòu)大整數(shù)運(yùn)算是一些相當(dāng)復(fù)雜的運(yùn)算，本文要實(shí)現(xiàn)的是大整數(shù)基本運(yùn)算，采用模塊化思想按照層次結(jié)構(gòu)來(lái)設(shè)計(jì)及實(shí)現(xiàn)一些其它的輔助函數(shù)，而

19、不是把它們內(nèi)嵌在算法函數(shù)內(nèi)，這樣既能夠避免算法函數(shù)的程序代碼的過(guò)分冗長(zhǎng)，使代碼清晰易懂、突出算法過(guò)程又能夠使程序易于測(cè)試、排錯(cuò)、更新和復(fù)用。由于本文是介紹大整數(shù)的基本算法，在本文開(kāi)始之前只介紹一些關(guān)鍵的輔助函數(shù)，其它輔助函數(shù)是在相關(guān)算法實(shí)現(xiàn)的時(shí)候再簡(jiǎn)略介紹它的功能。2.1 大整數(shù)的存取結(jié)構(gòu)大整數(shù)的存取結(jié)構(gòu)2.1.1 大整數(shù)結(jié)構(gòu)分析大數(shù)的存儲(chǔ)方式主要是有兩種鏈?zhǔn)酱鎯?chǔ)方式和順序存儲(chǔ)方式。一是采用鏈表作為存儲(chǔ)結(jié)構(gòu)，這種方式可以適應(yīng)不定長(zhǎng)度的大數(shù)，這種方式的存儲(chǔ)空間包括整數(shù)表示部分和鏈表指針部分，其空間利用率不高，而且其存儲(chǔ)空間是離散的，所以隨機(jī)訪問(wèn)效率也不高，而且頻繁的堆操作和引用操作勢(shì)必大量增加開(kāi)

20、銷，不利于編譯器優(yōu)化速度；另外，根據(jù)內(nèi)存管理方式的不同，順序存儲(chǔ)方式可以再分為靜態(tài)存儲(chǔ)方式和動(dòng)態(tài)存儲(chǔ)方式。靜態(tài)存儲(chǔ)方式數(shù)組的大小是事先已經(jīng)知道的，適合知道大小的整數(shù)運(yùn)算。而因其數(shù)組長(zhǎng)度是固定不變的，在運(yùn)算的時(shí)候容易造成溢出。所以其不適合不定長(zhǎng)度的整數(shù)運(yùn)算。而動(dòng)態(tài)方式，其可以動(dòng)態(tài)分配內(nèi)存空間?？梢愿鶕?jù)整數(shù)位數(shù)的變化調(diào)整大小。其是最常用的順序存儲(chǔ)方式，而且順序存儲(chǔ)方式是連續(xù)分配空間，所以其可以實(shí)現(xiàn)隨機(jī)訪問(wèn)，提高速度，因?yàn)榇鎯?chǔ)空間就是整數(shù)本身，沒(méi)有其他額為開(kāi)銷，所以空間利用率也較高。由于受到計(jì)算機(jī)字長(zhǎng)的限制制約著大整數(shù)的運(yùn)算，所以必須要解決大整數(shù)表示問(wèn)題，通常是采用 b 進(jìn)制表示，如，其表示為：0

21、1 2(.)bxnx x xx（） ，而且系數(shù)（）必1210121*.*nnnnnxx bx bx bxbx00 x0 x0in 須是計(jì)算機(jī)可以表示的常數(shù)。在基選擇上，最容易想到也是最直接易懂的是用整數(shù)數(shù)組來(lái)保存大數(shù)，數(shù)組的每個(gè)元素保存大數(shù)的一個(gè)十進(jìn)制數(shù)字，這種方式操作比較簡(jiǎn)單，但這種方式需要較多的額外運(yùn)算，而且效率明顯不高，也需要比較多的存儲(chǔ)空間；效率比較高的，被采用的比較多的方式是用 b 進(jìn)制數(shù)組存儲(chǔ)大數(shù)，即把大數(shù)轉(zhuǎn)化 b 進(jìn)制表示，數(shù)組的每個(gè)元素存儲(chǔ)這個(gè) b 進(jìn)制數(shù)的一個(gè) b 進(jìn)制的數(shù)位，這樣既方便計(jì)算機(jī)處理又提高了內(nèi)存的利用率，同時(shí)縮短了大數(shù)的實(shí)際表示長(zhǎng)度，減少了循環(huán)的次數(shù)，有利于提高

22、效率。為了更好的適應(yīng)各種算法的需要及避免過(guò)度浪費(fèi)存儲(chǔ)空間，本文采用多精度的方式。1985 年，西安交通大學(xué)的王永祥副教授曾經(jīng)采用過(guò)萬(wàn)進(jìn)制的方法表示大數(shù)，并實(shí)現(xiàn)了自己的大數(shù)算法11。根據(jù)萬(wàn)進(jìn)制的原理，本文決定將整數(shù)進(jìn)制 b 取為 2 的某次冪。本文是基于 32 位系統(tǒng)，vc+有_int64 這樣的 64 位整數(shù)類型，但 32 位硬件上畢竟不能直接處理 64 位整數(shù)，那勢(shì)必需要附加內(nèi)部操作來(lái)完成。為了匹配硬件操作，取 b 進(jìn)制為半個(gè) cpu 字長(zhǎng)的 unsigned short int 型，即 216進(jìn)制. 由于 m 位的數(shù)乘以 n 位的數(shù)最多將產(chǎn)生 m+n 位的數(shù),所以兩個(gè) 216進(jìn)制數(shù)位的乘積

23、可以用一個(gè) 232數(shù)來(lái)保存而不超出cpu 的字長(zhǎng)。2.1.2 大整數(shù)結(jié)構(gòu)為了模塊化編程,程序結(jié)構(gòu)清晰易懂。本文在開(kāi)始之前先對(duì)大整數(shù)做一個(gè)結(jié)構(gòu)封裝，使用一個(gè)結(jié)構(gòu)體來(lái)表示大整數(shù)。標(biāo)示符 mbigint 表示一個(gè)多精度的大整數(shù)結(jié)構(gòu)：typedef struct/* 定義大整數(shù)的結(jié)構(gòu) */long int alloclen; /* 記錄數(shù)組已經(jīng)分配總的空間大小 */long int length; /* 記錄大整數(shù)的長(zhǎng)度，即系數(shù)的個(gè)數(shù) */int sign; /* 記錄大整數(shù)的符號(hào) */un_short *pbigint;/* 指向大整數(shù)的數(shù)據(jù)的指針，即指向系數(shù)的地址 */ mbigint;上面大整數(shù)

24、封裝的結(jié)構(gòu)中，分別記錄大整數(shù)分配到的空間 alloclen 大小和已經(jīng)在使用到的空間 length 大小。使用這種結(jié)構(gòu)能夠有效地管理內(nèi)存，減少堆操作的次數(shù)，減少相關(guān)操作帶來(lái)的性能損失；通過(guò)一個(gè)指針來(lái)指向保存大整數(shù)的數(shù)據(jù)的數(shù)組，這樣有利于內(nèi)存的動(dòng)態(tài)調(diào)整，可以不移動(dòng)數(shù)組的任何元素而交換兩個(gè)大整數(shù)，其只需要交換三個(gè)內(nèi)置的整數(shù)值和一個(gè)指針就可以了。本文所討論的大整數(shù)的數(shù)位是按照低位在前的方式存放，則按從低位到高位的順序把大整數(shù)的數(shù)位按下標(biāo)從小到大順序存放到數(shù)組中去，也就是十進(jìn)制表示方式相反方向，這樣既有利于擴(kuò)展大數(shù)的長(zhǎng)度也有利于縮減。2.2 預(yù)定義的變量預(yù)定義的變量因?yàn)樵诰幊痰臅r(shí)候很多的變量字符比較長(zhǎng)

25、，很容易略寫(xiě)某個(gè)字符，造成編程錯(cuò)誤，所以本文首先對(duì)一些變量進(jìn)行預(yù)定義。typedef unsigned short int un_short;/*16 位數(shù)的聲明符號(hào)*/ypedef unsigned long int un_long; /*32 位數(shù)的聲明符號(hào)*/#define bit_pre_word16ul /* 每個(gè)單精度數(shù)字含有的 bit 數(shù) */* 定義信號(hào)標(biāo)識(shí) */return_ok_bint1 /* 正常返回 */return_faile_bint 0 /*錯(cuò)誤返回*/initial_bint 49 /*默認(rèn)分配的大小*/step_biint 16 /*起跳值*/對(duì)于大整數(shù)的符

26、號(hào)，本文只區(qū)分正數(shù)與負(fù)數(shù)，若大整數(shù)的 sign 分量為 1 則表示該大整數(shù)是正數(shù)，這要求其它函數(shù)在運(yùn)算到使 sign 分量為-1 的保證設(shè)置該大整數(shù)為負(fù)。用 un_short 表示大整數(shù)的一位數(shù)字，一下簡(jiǎn)稱單字或字，兩倍于 un_short 大小的則稱為雙字，三倍于 un_short 大小的則稱為三字，由于雙字用 un_long 來(lái)表示，已經(jīng)達(dá)到了32 位 cpu 的字長(zhǎng)。所以在需要三字的地方本程序通過(guò)模擬的方式達(dá)到相關(guān)效果，詳細(xì)見(jiàn)后面介紹。2.3 大整數(shù)基本函數(shù)定義大整數(shù)基本函數(shù)定義 因?yàn)樵诖笳麛?shù)的基本運(yùn)算中，很多的操作都是類似和重復(fù)的，所以本文在開(kāi)始介紹基本運(yùn)算之前，先對(duì)這些基礎(chǔ)函數(shù)進(jìn)行說(shuō)

27、明。2.3.1 大整數(shù)初始化操作函數(shù) initmbint(mbigint *bint, long int size = 49)的目的是初始化一個(gè)大整數(shù)，默認(rèn)長(zhǎng)度是 49 字節(jié)。因?yàn)椴捎昧藙?dòng)態(tài)分配內(nèi)存的方式，所以大整數(shù)需要一些函數(shù)處理堆上的操作。為了在整數(shù)基本運(yùn)算中減少多次進(jìn)行堆操作，本函數(shù)分配的內(nèi)存大小有個(gè)初始值 initial_bint，如果大整數(shù)的輸入大小 size 小于該值，則都會(huì)分配該值大小的數(shù)位。否則在起跳值的基礎(chǔ)上以步長(zhǎng) step_biint 為增量進(jìn)行遞加直到大于 size，然后分配該大小的數(shù)位。成功分配后所有數(shù)據(jù)位都被置為 0，符號(hào)標(biāo)記為非負(fù)。在本實(shí)現(xiàn)中，初始值 initial

28、_bint 在頭文件中被定義為 48+1 即每個(gè)大整數(shù)的最小長(zhǎng)度為48*16+1*16bit，而步長(zhǎng) step_bint 在頭文件中被定義為 16 即 256bit，因?yàn)?512bit 的公鑰算法已經(jīng)不安全，所以本程序從 768bit 起跳，要多加 16bit 是因?yàn)楹芏喙€算法的長(zhǎng)度都是 512 的倍數(shù)，如果大整數(shù)的長(zhǎng)度剛好等于公鑰算法的長(zhǎng)度則很多時(shí)候會(huì)引起不必要的擴(kuò)充內(nèi)存的操作，所以本程序加了 16bit 的零頭。2.3.2 大整數(shù)的銷毀操作函數(shù) deletembint(mbigint *bint)用于釋放大整數(shù)所得的堆內(nèi)存，并將符號(hào)標(biāo)記為非負(fù)，要再次使用該數(shù)則必須先重新初始化；在較復(fù)雜的

29、函數(shù)中，若某一步（例如調(diào)用子函數(shù)）執(zhí)行失敗，則需要調(diào)用 deletembint 函數(shù)釋放該一步之前初始化的所有的大整數(shù)以免做成內(nèi)存泄漏。2.3.3 大整數(shù)的擴(kuò)展擴(kuò)展是指在運(yùn)算操作的時(shí)候，結(jié)果超出了現(xiàn)在大整數(shù)的大小就追加空間，使得大整數(shù)能夠得到足夠空間來(lái)存儲(chǔ)數(shù)據(jù)。extendmbint(mbigint *bi,long int size)以step_bint 為增量在原來(lái)的大小上遞加直到大于 size，然后分配該大小的數(shù)位保存數(shù)據(jù)。2.3.4 大整數(shù)的輸入和輸出函數(shù)因?yàn)槲覀冏顬槭煜さ臄?shù)字和使用的最多的也是十進(jìn)制表示形式，所以本文對(duì)大整數(shù)的輸入和輸出都是使用十進(jìn)制形式。函數(shù) read_radix(

30、mbigint *bi,char *str)是將十進(jìn)制表示的字符串讀入并轉(zhuǎn)換為大整數(shù)結(jié)構(gòu)表示；函數(shù) write_radix(mbigint *bi,char *str)將大整數(shù)轉(zhuǎn)換為十進(jìn)制的字符串表示。當(dāng)然可以通過(guò)對(duì)以上兩個(gè)函數(shù)的修改，形成不同的 b 進(jìn)制輸入和輸出方式。2.4 大整數(shù)的移位函數(shù)大整數(shù)的移位函數(shù)2.4.1 字移位運(yùn)算 字移位是指對(duì)大整數(shù)左移或右移動(dòng) 16 個(gè)比特位，即大整數(shù)數(shù)組的一個(gè)元素的大小。從大整數(shù)的結(jié)構(gòu)可以知道， 將大整數(shù)轉(zhuǎn)換成了 b 進(jìn)制數(shù)數(shù)組，此時(shí)可以將大整數(shù)看成是 b 的多項(xiàng)式，則大整數(shù) a 可以很方便地看成，那么110nnnna baba或者的運(yùn)算就可以通過(guò)將數(shù)組

31、的元素向左或向右移動(dòng) b 個(gè) b 進(jìn)制數(shù)位的*ba b/ba b方式快速地完成，算法復(fù)雜度僅為 o(n)，速度大大得提高了。函數(shù)left_shift_word(bigintmp * dst,long int n)用于將大整數(shù) dst 左移 n 個(gè)字即乘以 bn；而函數(shù) right_shift_word(bigintmp * dst,long int n)則用于將 dst 右移 n 個(gè)字，這相當(dāng)于除以bn。1、字左移運(yùn)算字左移運(yùn)算就是對(duì)整數(shù)進(jìn)行一次乘法運(yùn)算，乘數(shù)是基 b 的 n 次方?？梢酝ㄟ^(guò)簡(jiǎn)單的節(jié)點(diǎn)左移得到。/左移 n 個(gè)字int left_shift_word(mbigint *dst,

32、long int n) /為目標(biāo)數(shù)組分配足夠多空間if(dst-length + n dst-alloclen) int result = 0;if(result = extendmbint(dst,dst-length+n) != return_ok_bint)return result;for(int i = dst-length-1; i = 0; i-) /左移 n 個(gè)字dst-pbigint i+ n = dst-pbigint i ;for(i = 0;i pbigint i = 0;dst-length += n; /大整數(shù)長(zhǎng)度的設(shè)置return return_ok_bint;運(yùn)

33、算結(jié)果如下：圖 2.1 左移字運(yùn)算結(jié)果2、字右移運(yùn)算，其實(shí)就是對(duì)整數(shù)進(jìn)行一次除法運(yùn)算。除數(shù)是基 b 的 n 次方?？梢酝ㄟ^(guò)簡(jiǎn)單的節(jié)點(diǎn)左移得到。但其僅是計(jì)算商，而不保存余數(shù)。/右移 n 個(gè)字int right_shift_word(mbigint *dst, long int n)int len = dst-length; /大整數(shù)的長(zhǎng)度f(wàn)or(int i = 0;i length; i+)/右移 n 個(gè)字dst-pbigint i = dst-pbigint i+n ;for(i; i pbigint i = 0; dst-length -= n; /重設(shè)置大整數(shù)長(zhǎng)度return return

34、_ok_bint;運(yùn)算結(jié)果如下：圖 2.2 右移字運(yùn)算結(jié)果2.4.2 比特移位運(yùn)算比特移位是指對(duì)大整數(shù)進(jìn)行一個(gè)比特的左移或右移。根據(jù)大整數(shù)的結(jié)構(gòu)定義，大整數(shù)的基是 2 的冪。所以大整數(shù)乘以或除以 2 都可以通過(guò)簡(jiǎn)單的左移一位或右移一位得到結(jié)果。左移一個(gè)比特就是對(duì)大整數(shù)進(jìn)行乘以 2 操作，右移的時(shí)候就是對(duì)大整數(shù)進(jìn)行除以 2 操作，其也僅是得到除以 2 的商，而沒(méi)有保存余數(shù)。1、大整數(shù)左移一個(gè)比特位 /左移一位運(yùn)算int left_shift_bit(mbigint *dst, mbigint *src)long int len = 0; /用來(lái)保存目的操作數(shù)的程度long int i = 0;u

35、nsigned int carry = 0;un_short *pdst = dst-pbigint; /指向目的大整數(shù)存取數(shù)組的指針un_short *psrc = src-pbigint; /指向源大整數(shù)存取數(shù)組的指針if(dst-alloclen length+1 ) / 確保目的大整數(shù)能夠容納移位后的結(jié)果int result = 0;if(result = extendmbint(dst,src-length + 1) != return_ok_bint) /*擴(kuò)大大整數(shù)空間，保證能夠存儲(chǔ)*/return result;pdst = dst-pbigint; /記錄目的操作數(shù)原來(lái)的已用

36、空間，方便后面處理len = dst-length; dst-length = src-length;psrc = src-pbigint;/源大整數(shù)數(shù)組元素分別左移一位，并賦給目的大整數(shù)for(i = 0; i length; +i)pdsti = (un_short)(carry = (psrci) 16);if(carry 16) != 0) /*若最高數(shù)位左移后溢出，則將溢出的比特存到下一個(gè)字*/pdstsrc-length = (un_short)(carry 16);+(dst-length);for(i = dst-length; i sign = src-sign; /符號(hào)更改

37、return return_ok_bint; 運(yùn)算結(jié)果如下：圖 2.3 左移一比特運(yùn)算結(jié)果1、大整數(shù)右移一個(gè)比特位/右移一位運(yùn)算int right_shift_bit(mbigint *dst,mbigint *src)long int oldlen = 0; /保存目的大整數(shù)的原來(lái)長(zhǎng)度long int i = 0;unsigned int carry = 0;un_short temp = 0; un_short *pdst = dst-pbigint; /目的大整數(shù)數(shù)組指針un_short *psrc = src-pbigint; /源大整數(shù)數(shù)組指針if(dst-alloclen leng

38、th) /確保目的大整數(shù)能夠容納移位后的結(jié)果int result = 0;/擴(kuò)展目的大整數(shù)長(zhǎng)度if(result = extendmbint(dst,src-length) != return_ok_bint) return result; pdst = dst-pbigint;oldlen = dst-length;dst-length = src-length;psrc = src-pbigint;for(i = src-length -1; i = 0; -i) /* 分別右移一位*/temp = (un_short)(psrci 1) | (un_short)(carry length

39、; i sign = src-sign; /符號(hào)賦值oldlen=dst-alloclen; pdst=dst-pbigint+dst-alloclen-1;while(0=*pdst-) /重新計(jì)算出目的大整數(shù)的長(zhǎng)度值oldlen-;dst-length=oldlen;return return_ok_bint;運(yùn)算結(jié)果如下：圖 2.4 右移一比特運(yùn)算結(jié)果3 大整數(shù)加法和減法實(shí)現(xiàn)大整數(shù)加法和減法實(shí)現(xiàn)由于大整數(shù)有正負(fù)之分，所以兩個(gè)大整數(shù)相加有四種情況：a+b，a+（-b） ， （-a）+b 和-a+（-b） 。對(duì)于 a+b 和-a+(-b)，可以通過(guò)對(duì)數(shù)組對(duì)應(yīng)位元素相加即可，主要是考慮進(jìn)位問(wèn)題

40、。而 a+（-b）和（-a）+b，其實(shí)就是兩個(gè)大整數(shù)的減法，其主要考慮的問(wèn)題是向高位借位的問(wèn)題。所以減法可以通過(guò)加法的運(yùn)算得到結(jié)果。3.1 符號(hào)相同的加法運(yùn)算符號(hào)相同的加法運(yùn)算 符號(hào)相同的加法運(yùn)算的實(shí)現(xiàn)過(guò)程是基于這樣的一個(gè)原因：因?yàn)閮蓚€(gè)整數(shù)的符號(hào)相同，可以直接對(duì)兩個(gè)整數(shù)數(shù)組對(duì)應(yīng)位元素相加，并考慮進(jìn)位問(wèn)題。因?yàn)閮蓚€(gè)整數(shù)的數(shù)位存在以下三種情況（不妨設(shè)兩個(gè)大整數(shù)分別為 src1 和 src2）：src1-length = src2-length；src1-length src2-length； src1-length length。所以在處理加法的時(shí)候，對(duì)數(shù)位較大的整數(shù)一分為二，第一部分是跟另一大整

41、數(shù)的長(zhǎng)度相等?？梢韵劝严嗤L(zhǎng)度部分先計(jì)算，然后再對(duì)多出的長(zhǎng)度部分直接賦值，這樣可以不用考慮誰(shuí)大誰(shuí)小問(wèn)題，而且可以加快運(yùn)算速度。如下所示：表 3.1 分段運(yùn)算過(guò)程1 2 34 5 6 7 8 9 4 5 6 7 8 9 9 1 3 5 7 8 1 2 39 1 3 5 7 8 /符號(hào)相同的加法運(yùn)算實(shí)現(xiàn) int addmbint1(mbigint* dst, mbigint* src1, mbigint* src2) long int len = 0; /兩個(gè)大整數(shù)的長(zhǎng)度最大值 long int dstlen = 0; /目標(biāo)數(shù)組分配的最大值 un_short mark = 0;/進(jìn)位標(biāo)志 uns

42、igned int result;/數(shù)組對(duì)應(yīng)元素相加結(jié)果 long sign = src1-sign;/整數(shù)的符號(hào) int i = 0; len = (src1-length = src2-length)?src1-length:src2-length; dstlen = len; if(-1 = extendmbint(dst,len)/擴(kuò)展足夠內(nèi)存 return 0; /較小數(shù)位的整數(shù)的長(zhǎng)度 len = (src1-lengthsrc2-length)? src2-length: src1-length; for(i = 0; i pbiginti + src2-pbiginti + ma

43、rk; dst-pbiginti = (result&0 xffff); mark = result 16;/對(duì)第一個(gè)大整數(shù)數(shù)位多出部分進(jìn)行計(jì)算 if(src1-length src2-length) while(i length) result = src1-pbiginti + mark; dst-pbiginti = result & 0 xffff; mark = result 16; i+; if(mark != 0) dst-pbiginti = mark; dstlen = src1-length + 1; /對(duì)第二個(gè)大整數(shù)數(shù)位多出部分進(jìn)行計(jì)算else if(sr

44、c1-length length)while(i length)result = src2-pbiginti + mark;dst-pbiginti = result & 0 xffff;mark = result 16;i+;if(mark != 0)dst-pbiginti = mark;dstlen = src2-length + 1; dst-sign = sign; /符號(hào)的更改 dst-length = dstlen; / 長(zhǎng)度設(shè)置 return 1; 運(yùn)行結(jié)果如下：圖 3.1 符號(hào)相同的加法運(yùn)算結(jié)果3.2 符號(hào)不相同的加法運(yùn)算符號(hào)不相同的加法運(yùn)算 符號(hào)不同的加法運(yùn)算的過(guò)程

45、，也是跟符號(hào)相同的加法過(guò)程類似。也是對(duì)數(shù)位較大的整數(shù)進(jìn)行分段，不過(guò)，它也有不同的地方。因?yàn)榉?hào)不相同，這個(gè)加法就是減法。因?yàn)椴恢朗悄膫€(gè)大整數(shù)較大，當(dāng)它們做減法運(yùn)算的時(shí)候，就有可能會(huì)在最高數(shù)位出現(xiàn)負(fù)數(shù)問(wèn)題，而大整數(shù)各位元素都為正數(shù)，所以要多處理一步，即對(duì)負(fù)數(shù)轉(zhuǎn)換成正整。而如果把無(wú)符號(hào)整數(shù)的較大者作為被減數(shù)，就可以省略這一步。所以此運(yùn)算過(guò)程是：先對(duì)兩個(gè)大整數(shù)進(jìn)行無(wú)符號(hào)比較，最大者作為被減數(shù)，然后進(jìn)行減法操作。/符號(hào)不相同的加法運(yùn)算（減法運(yùn)算）int addmbint2(mbigint* dst, mbigint* src1, mbigint* src2)long int len = 0; /兩個(gè)

46、大整數(shù)的長(zhǎng)度最大值un_short len1 = 0;long int dstlen = dst-alloclen; /目標(biāo)數(shù)組分配的最大值un_short mark = 0;/進(jìn)位標(biāo)志 int result = 0;/數(shù)組對(duì)應(yīng)元素相加結(jié)果int sign = src1-sign;/整數(shù)的符號(hào)int i = 0;len = (src1-length src2-length)? src1-length: src2-length;len1 = (src1-length src2-length)? src2-length: src1-length;un_short *psrc1=src1 - pbi

47、gint,*psrc2 = src2-pbigint,*pdst = null; if(-1 = extendmbint(dst,len)return 0;/擴(kuò)展足夠內(nèi)存int re = comparembint(src1,src2); /對(duì)兩個(gè)大整數(shù)進(jìn)行無(wú)符號(hào)比較if(re = 0) /兩個(gè)大整數(shù)大小相等，進(jìn)行加法運(yùn)算后位 0dst - length = 0;dst - sign = 0;return 1;if(re = -1)/無(wú)符號(hào)比較，大整數(shù) src2 比大整數(shù) src1 大sign = src2-sign;psrc1 = src2-pbigint;psrc2 = src1-pbigi

48、nt;len1 = src1-length;for(i = 0;i len1; i+)/對(duì)兩整數(shù)相同長(zhǎng)度部分進(jìn)行計(jì)算if(result = (psrc1i - psrc2i - mark)pbiginti = result;while(i = 0)dst-pbiginti + = result;mark = 0;else /表示向高一位借了 1dst-pbigint i + = result + 65536; dst-length = len; /長(zhǎng)度設(shè)置dst-sign = sign; /符號(hào)位設(shè)置trimmbint(dst); /對(duì)結(jié)果去掉前面的 0return 1;運(yùn)算結(jié)果如下：圖 3.

49、2 減法運(yùn)算結(jié)果4 大整數(shù)乘法實(shí)現(xiàn)大整數(shù)乘法實(shí)現(xiàn)現(xiàn)在流行的公鑰算法很多都是以模冪為基礎(chǔ)的，而計(jì)算模冪的過(guò)程中大量地使用了乘法，所以乘法非常重要。然而，通用的乘法都需要 o()次的基本運(yùn)算，直到2n1962 年發(fā)現(xiàn)了 karatsuba 乘法人們才有了歷史的突破，同時(shí)該技術(shù)也促使人們發(fā)現(xiàn)了更多的有效算法，如基于傅立葉變換的方法。4.1 筆算乘法筆算乘法對(duì)于 m 位和 n 位的輸入，傳統(tǒng)的乘法需要 m*n 次基本的乘法，也即算法復(fù)雜度為o()。我們用紙和筆做乘法運(yùn)算時(shí)，用乘數(shù)的每一位乘以被乘數(shù)的每一位并加上上一2n列的進(jìn)位而產(chǎn)生一行適當(dāng)移位的中間結(jié)果，然后再將各行中間結(jié)果相加即得到乘法的最終結(jié)果，

50、例如 10 進(jìn)制下計(jì)算 456*32 的過(guò)程如表 4.1：表 4.1 筆算乘法的運(yùn)算過(guò)程456*32912136814592本算法按照上述過(guò)程進(jìn)行計(jì)算，但在計(jì)算機(jī)上最好是把內(nèi)部的乘法和加法并行的執(zhí)行，即計(jì)算每一行中間結(jié)果的同時(shí)將該行加到最終結(jié)果上，這樣既可以省去不少步驟，也避免了中間結(jié)果的空間開(kāi)銷和內(nèi)存管理操作，這個(gè)簡(jiǎn)單的優(yōu)化能夠一定程度上提高效率。本算法的偽代碼如表 4.2：表 4.2 筆算乘法算法輸入：分別含有 n 和 t 個(gè) b 進(jìn)制數(shù)位的大整數(shù) x、y輸出：b 進(jìn)制的乘積110n twww w 1. i 從 0 到 n+t-1,置 wi = 02. i 從 0 到 t2.1 c 02.

51、2 j 從 0 到 n計(jì)算 ijjiuvwxyc置,ijwv cu2.3 1i nwu 3. 返回110n twww w 由于兩個(gè) 16 位的乘積將超過(guò) 16 位所能表示的最大數(shù)，我們知道一個(gè) 32 位的數(shù)能夠完整地保存兩個(gè) 16 位數(shù)的乘積，上面的偽碼中用一個(gè) 32 位來(lái)保存兩個(gè) 16 位的數(shù)乘積再加上兩個(gè)單字后的結(jié)果，下面討論一下它的安全性（是否會(huì)產(chǎn)生溢出）：上面表達(dá)式計(jì)算的最大的結(jié)果為，化簡(jiǎn)后為，正好 16161616212121213221是一個(gè) 32 位數(shù)的最大值，所以一個(gè) 32 位數(shù)能夠保存該表達(dá)式的結(jié)果而不產(chǎn)生溢出，程序不會(huì)損失精度。/筆算乘法實(shí)現(xiàn)代碼 int mulbasicm

52、bint(mbigint *product, mbigint *bia, mbigint *bib)mbigint bit;/計(jì)算結(jié)果先保存在臨時(shí)變量中unsigned int carry = 0;/這個(gè)雙字用于保存中間結(jié)果register un_short *pworda = bia-pbigint;register un_short *pwordb = bib-pbigint;register un_short *pprd = null;int result = 0;long int i = 0;long int j = 0; /初始化臨時(shí)大整數(shù)變量if(result = initmbin

53、t(&bit,bia-length + bib-length) != return_ok_bint)return result;bit.length = bia-length + bib-length;bit.sign = (bia-sign = bib-sign) ? 1: -1;/設(shè)置符號(hào)pprd = bit.pbigint;for(i = 0; i length; +i) / 按傳統(tǒng)的紙筆乘法的方式計(jì)算乘積carry = 0;for(j = 0; j length; +j)pprdi + j = (un_short)(carry = (unsigned int)pprdi + j

54、+ (unsigned int)pwordai * (unsigned int)pwordbj + (unsigned int)(un_short)(carry 16);pprdi + j += (un_short)(carry 16);/最后可能的進(jìn)位trimmbint(&bit);/去除高位無(wú)效的 0swapmbint(product,&bit);/交換兩個(gè)大整數(shù)deletembint(&bit); /清除臨時(shí)變量return return_ok_bint;乘法運(yùn)算結(jié)果如下：圖 4.1 筆算乘法運(yùn)算結(jié)果4.2 使用使用 comba 方法的快速乘法方法的快速乘法傳統(tǒng)的

55、筆算乘法有一個(gè)不好的地方是它處理每一個(gè)數(shù)位的時(shí)候都需要處理向上進(jìn)位，paul g.comba 曾經(jīng)描述了一種無(wú)需嵌套進(jìn)位運(yùn)算的來(lái)完成乘法的方法。在傳統(tǒng)的筆計(jì)算乘法過(guò)程中，要計(jì)算各行中間乘積，然后將各行加在一起，從而形成最終結(jié)果，comba 方法的核心仍然是筆算乘法，不過(guò) comba 方法不是每次計(jì)算一行，而是一列。在 comba 算法中，結(jié)果的各列是獨(dú)立的，它在每次計(jì)算最終結(jié)果的一列，到最后才將各列的進(jìn)位從低到高向前推進(jìn)，大大的減少了進(jìn)位的處理次數(shù)。comba 算法在十進(jìn)制下計(jì)算 465*34 的過(guò)程如表 4.4 所示。表 4.3 comba 乘法過(guò)程465*344*4=164*6=244*5

56、=203*4=123*6+16=343*5+24=391234392015810comba 乘法的第一步是計(jì)算每一列的結(jié)果得到向量12,34,39,20，然后從低位到高位修正各列的結(jié)果，完成適當(dāng)?shù)倪M(jìn)位。該算法的確能夠省掉不少進(jìn)位操作，不過(guò)該算法明顯帶來(lái)了另一個(gè)問(wèn)題如何保存每一列的結(jié)果，兩個(gè) 16 位的數(shù)的乘積要一個(gè) 32位數(shù)才能安全保存，而乘法的過(guò)程中一列可能會(huì)有很多組單字的乘積。libtommath 大數(shù)庫(kù)12由于采用了特殊的進(jìn)制，它可以比較輕松地處理這個(gè)問(wèn)題，libtommath 大數(shù)庫(kù)采用 28bit 存儲(chǔ)一個(gè)單字，用 64bit 存儲(chǔ)一個(gè)雙字，因此它一個(gè)雙字可以存儲(chǔ)組單字與單字的乘積，

57、只要保證筆計(jì)算的中間過(guò)程不超過(guò) 256 行（即乘64562/2256數(shù)不能超過(guò) 256 個(gè)數(shù)位）就可以安全使用 comba 算法提高乘法的速率了。其實(shí) 256 個(gè)28bit 的數(shù)位已經(jīng)可以表示 7168bit 的大整數(shù)了，遠(yuǎn)遠(yuǎn)超出了現(xiàn)行流行的 1024bit 或者2048bit 的需要，就算真的需要計(jì)算長(zhǎng)于 7168bit 的大整數(shù)也沒(méi)關(guān)系，因?yàn)楫?dāng)大整數(shù)長(zhǎng)度超過(guò) 2240bit 時(shí) libtommath 庫(kù)便會(huì)自動(dòng)地使用效率更好的 karatsuba 算法。本程序用 32bit 存儲(chǔ)一個(gè)雙字，用 16bit 存儲(chǔ)一個(gè)單字，單字的長(zhǎng)度已經(jīng)不能再短了，否則就影響性能（增加了循環(huán)的次數(shù)） ，所以 l

58、ibtommath 的做法不適合本程序，而且為了這個(gè)而使每個(gè)字浪費(fèi) 4bit 的做法也不特別好的做法。在本算法中，使用兩個(gè)雙字來(lái)模擬一個(gè)三字（三倍于單字的長(zhǎng)度） ，這時(shí)乘數(shù)的長(zhǎng)度不能超過(guò) 65536 個(gè)數(shù)位（約 1 百萬(wàn)bit） ，同時(shí)本算法將計(jì)算每一列的和的過(guò)程和處理最后向前進(jìn)位的過(guò)程并行執(zhí)行從而省去存儲(chǔ)向量的操作。int mulcombambint(mbigint *product,mbigint *bia,mbigint *bib)mbigint bit; /臨時(shí)大整數(shù)變量聲明unsigned int high = 0;/使用了兩個(gè)雙字來(lái)模擬一個(gè)三字，保存一列結(jié)果unsigned int

59、 low = 0;register un_short *pworda = bia-pbigint; /寄存器變量，加快訪問(wèn)速度register un_short *pwordb = bib-pbigint;register un_short *pprd = null;int result = 0;long int i = 0;long int k = 0; /初始化臨時(shí)大整數(shù)變量if(result = initmbint(&bit,bia-length+ bib-length) != return_ok_bint)return result;bit.length= bia-length

60、 + bib-length; /結(jié)果長(zhǎng)度bit.sign = (bia-sign = bib-sign) ? 1 : -1; /結(jié)果符號(hào)pprd = bit.pbigint;for(k = 0; k = 16;for(i = 0; i = k; +i)if(i length) & (k-i) length)low += (unsigned int)pwordai * (unsigned int)pwordbk - i;high += low 16; /high 保存高位的兩個(gè)字low = (unsigned int)(un_short)low; /low 只保存低位字pprdk = (un_short)low;trimmbint(&bit); /消除高位的無(wú)效 0swapmbint(prod