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

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

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

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

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

5、采用 c/c+語言編寫，所采用的優(yōu)化也均建立在 c/c+語言這一層面上，在保證算法有足夠高的效率的同時力求代碼清晰易懂，函數(shù)接口簡單明了，具有可移植性和穩(wěn)定性。關鍵詞：關鍵詞：多精度大整數(shù)，comba，montgomery，二分查找，筆算 注：本設計（論文）題目來源于企業(yè)項目。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 國內外研究狀況.11.3 本文研究內容.22 大整數(shù)的結構大整數(shù)的結構.32.1 大整數(shù)的存取結構.32.1.1 大整數(shù)結構分析.32.1.2 大整數(shù)結構.42.2 預定義的變量.52.3 大整數(shù)基本函數(shù)定義.52.3.1 大整數(shù)初始化操作.52.3.2 大整數(shù)的銷毀操作.62.3.3 大整數(shù)的擴展.62.3.4 大整數(shù)的輸入和輸出函數(shù).62.4 大整數(shù)的移位函數(shù).72.4.1 字移位運算.7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26、號，本文只區(qū)分正數(shù)與負數(shù)，若大整數(shù)的 sign 分量為 1 則表示該大整數(shù)是正數(shù)，這要求其它函數(shù)在運算到使 sign 分量為-1 的保證設置該大整數(shù)為負。用 un_short 表示大整數(shù)的一位數(shù)字，一下簡稱單字或字，兩倍于 un_short 大小的則稱為雙字，三倍于 un_short 大小的則稱為三字，由于雙字用 un_long 來表示，已經達到了32 位 cpu 的字長。所以在需要三字的地方本程序通過模擬的方式達到相關效果，詳細見后面介紹。2.3 大整數(shù)基本函數(shù)定義大整數(shù)基本函數(shù)定義 因為在大整數(shù)的基本運算中，很多的操作都是類似和重復的，所以本文在開始介紹基本運算之前，先對這些基礎函數(shù)進行說

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

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

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

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

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

32、long int n) /為目標數(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 個字dst-pbigint i+ n = dst-pbigint i ;for(i = 0;i pbigint i = 0;dst-length += n; /大整數(shù)長度的設置return return_ok_bint;運

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

34、_ok_bint;運算結果如下：圖 2.2 右移字運算結果2.4.2 比特移位運算比特移位是指對大整數(shù)進行一個比特的左移或右移。根據(jù)大整數(shù)的結構定義，大整數(shù)的基是 2 的冪。所以大整數(shù)乘以或除以 2 都可以通過簡單的左移一位或右移一位得到結果。左移一個比特就是對大整數(shù)進行乘以 2 操作，右移的時候就是對大整數(shù)進行除以 2 操作，其也僅是得到除以 2 的商，而沒有保存余數(shù)。1、大整數(shù)左移一個比特位 /左移一位運算int left_shift_bit(mbigint *dst, mbigint *src)long int len = 0; /用來保存目的操作數(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ù)能夠容納移位后的結果int result = 0;if(result = extendmbint(dst,src-length + 1) != return_ok_bint) /*擴大大整數(shù)空間，保證能夠存儲*/return result;pdst = dst-pbigint; /記錄目的操作數(shù)原來的已用

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ù)位左移后溢出，則將溢出的比特存到下一個字*/pdstsrc-length = (un_short)(carry 16);+(dst-length);for(i = dst-length; i sign = src-sign; /符號更改

37、return return_ok_bint; 運算結果如下：圖 2.3 左移一比特運算結果1、大整數(shù)右移一個比特位/右移一位運算int right_shift_bit(mbigint *dst,mbigint *src)long int oldlen = 0; /保存目的大整數(shù)的原來長度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ù)能夠容納移位后的結果int result = 0;/擴展目的大整數(shù)長度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; /符號賦值oldlen=dst-alloclen; pdst=dst-pbigint+dst-alloclen-1;while(0=*pdst-) /重新計算出目的大整數(shù)的長度值oldlen-;dst-length=oldlen;return return_ok_bint;運算結果如下：圖 2.4 右移一比特運算結果3 大整數(shù)加法和減法實現(xiàn)大整數(shù)加法和減法實現(xiàn)由于大整數(shù)有正負之分，所以兩個大整數(shù)相加有四種情況：a+b，a+（-b） ， （-a）+b 和-a+（-b） 。對于 a+b 和-a+(-b)，可以通過對數(shù)組對應位元素相加即可，主要是考慮進位問題

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

41、數(shù)的長度相等?？梢韵劝严嗤L度部分先計算，然后再對多出的長度部分直接賦值，這樣可以不用考慮誰大誰小問題，而且可以加快運算速度。如下所示：表 3.1 分段運算過程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 /符號相同的加法運算實現(xiàn) int addmbint1(mbigint* dst, mbigint* src1, mbigint* src2) long int len = 0; /兩個大整數(shù)的長度最大值 long int dstlen = 0; /目標數(shù)組分配的最大值 un_short mark = 0;/進位標志 uns

42、igned int result;/數(shù)組對應元素相加結果 long sign = src1-sign;/整數(shù)的符號 int i = 0; len = (src1-length = src2-length)?src1-length:src2-length; dstlen = len; if(-1 = extendmbint(dst,len)/擴展足夠內存 return 0; /較小數(shù)位的整數(shù)的長度 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;/對第一個大整數(shù)數(shù)位多出部分進行計算 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; /對第二個大整數(shù)數(shù)位多出部分進行計算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; /符號的更改 dst-length = dstlen; / 長度設置 return 1; 運行結果如下：圖 3.1 符號相同的加法運算結果3.2 符號不相同的加法運算符號不相同的加法運算 符號不同的加法運算的過程

45、，也是跟符號相同的加法過程類似。也是對數(shù)位較大的整數(shù)進行分段，不過，它也有不同的地方。因為符號不相同，這個加法就是減法。因為不知道是哪個大整數(shù)較大，當它們做減法運算的時候，就有可能會在最高數(shù)位出現(xiàn)負數(shù)問題，而大整數(shù)各位元素都為正數(shù)，所以要多處理一步，即對負數(shù)轉換成正整。而如果把無符號整數(shù)的較大者作為被減數(shù)，就可以省略這一步。所以此運算過程是：先對兩個大整數(shù)進行無符號比較，最大者作為被減數(shù)，然后進行減法操作。/符號不相同的加法運算（減法運算）int addmbint2(mbigint* dst, mbigint* src1, mbigint* src2)long int len = 0; /兩個

46、大整數(shù)的長度最大值un_short len1 = 0;long int dstlen = dst-alloclen; /目標數(shù)組分配的最大值un_short mark = 0;/進位標志 int result = 0;/數(shù)組對應元素相加結果int sign = src1-sign;/整數(shù)的符號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;/擴展足夠內存int re = comparembint(src1,src2); /對兩個大整數(shù)進行無符號比較if(re = 0) /兩個大整數(shù)大小相等，進行加法運算后位 0dst - length = 0;dst - sign = 0;return 1;if(re = -1)/無符號比較，大整數(shù) src2 比大整數(shù) src1 大sign = src2-sign;psrc1 = src2-pbigint;psrc2 = src1-pbigi

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

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

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

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

52、bint(mbigint *product, mbigint *bia, mbigint *bib)mbigint bit;/計算結果先保存在臨時變量中unsigned int carry = 0;/這個雙字用于保存中間結果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ù)變量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;/設置符號pprd = bit.pbigint;for(i = 0; i length; +i) / 按傳統(tǒng)的紙筆乘法的方式計算乘積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);/最后可能的進位trimmbint(&bit);/去除高位無效的 0swapmbint(product,&bit);/交換兩個大整數(shù)deletembint(&bit); /清除臨時變量return return_ok_bint;乘法運算結果如下：圖 4.1 筆算乘法運算結果4.2 使用使用 comba 方法的快速乘法方法的快速乘法傳統(tǒng)的

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

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

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

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

59、 low = 0;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 k = 0; /初始化臨時大整數(shù)變量if(result = initmbint(&bit,bia-length+ bib-length) != return_ok_bint)return result;bit.length= bia-length

60、 + bib-length; /結果長度bit.sign = (bia-sign = bib-sign) ? 1 : -1; /結果符號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 保存高位的兩個字low = (unsigned int)(un_short)low; /low 只保存低位字pprdk = (un_short)low;trimmbint(&bit); /消除高位的無效 0swapmbint(prod