BigNum Math：加密多精度算法的理論與實(shí)現(xiàn)

本書的誕生是我人生的一個(gè)有趣的經(jīng)歷。那段時(shí)期我從一個(gè)涉世未深的年輕人成長(zhǎng)為一個(gè)周游列國(guó)、結(jié)識(shí)了無數(shù)新朋友和同事的軟件開發(fā)者。這一切開始于2001年12月，大約5年前，我開始了一個(gè)后來名為L(zhǎng)ibTomCrypt的項(xiàng)目，該項(xiàng)目被業(yè)內(nèi)廣泛使用。

我從事LibTomCrypt項(xiàng)目的最初目的是想把我的精力集中在某些有建設(shè)性的事情上，同時(shí)學(xué)習(xí)一些新技能。從事該項(xiàng)目的第一年，我學(xué)會(huì)了如何組織產(chǎn)品、歸檔文件，以及如何進(jìn)行后續(xù)的支持和維護(hù)。大約在2002年冬季，我開始尋求另一個(gè)項(xiàng)目以打發(fā)時(shí)間。由于意識(shí)到LibTomCrypt缺乏數(shù)學(xué)支持，于是著手開發(fā)一個(gè)新的數(shù)學(xué)庫(kù)。

這樣LibTomMath項(xiàng)目就誕生了。它最初只是現(xiàn)有項(xiàng)目的補(bǔ)丁集，很快就發(fā)展為一個(gè)單獨(dú)的項(xiàng)目。從頭編寫這個(gè)數(shù)學(xué)庫(kù)是生產(chǎn)一個(gè)穩(wěn)定和獨(dú)立的產(chǎn)品的基本原則。我還學(xué)會(huì)了哪些算法可用來進(jìn)行如模冪等這樣的運(yùn)算。這個(gè)庫(kù)僅經(jīng)過幾個(gè)月的開發(fā)就非常穩(wěn)定和可靠，并且立即投入使用。

2003年夏，我又開始尋找另一個(gè)項(xiàng)目。由于意識(shí)到只實(shí)現(xiàn)這些數(shù)學(xué)例程不足以真正理解它們，于是我開始嘗試自己對(duì)它們進(jìn)行詮釋。在此過程中，我最終掌握了這些算法背后的概念。這些知識(shí)正是我想傳遞給讀者們的。本書實(shí)際上取材于我自己的網(wǎng)站（www. libtomcrypt.com）上的一些公開素材。

當(dāng)我向別人提起LibTom項(xiàng)目（共有6個(gè)）并且告訴他們我準(zhǔn)備公開發(fā)布時(shí)，他們都覺得很詫異。他們問我為什么這么做，尤其是為什么還要繼續(xù)免費(fèi)進(jìn)行下去。我能做出的最好的解釋就是 “因?yàn)槲夷軌颉薄＿@對(duì)于成人間的對(duì)話來說有些奇怪，并且過于簡(jiǎn)單。我通常進(jìn)一步解釋為“我有這個(gè)能力，并且我愿意”，這也許更能說明問題。我是第一個(gè)承認(rèn)我所做的并無特殊之處的人，也許還有其他人也這么看，那么我們就可以組成一個(gè)令人自豪的小團(tuán)體。我的LibTom項(xiàng)目是我正在以工具和知識(shí)的形式回饋社會(huì)、能給他人帶來幫助的東西。

我編寫本書是因?yàn)樗�能進(jìn)一步實(shí)現(xiàn)我的學(xué)術(shù)開放的目標(biāo)。LibTomMath的源代碼本身很容易領(lǐng)悟和學(xué)習(xí)。但有很多時(shí)候，純粹的C代碼不能恰當(dāng)?shù)亟忉尡緯�中的算法。本書首先解釋該�?kù)的基礎(chǔ)，然后再介紹更復(fù)雜的算法。偽代碼和源代碼的同時(shí)使用提供了全世界計(jì)算機(jī)專業(yè)學(xué)生更容易接受的“理論”和“實(shí)踐”的雙重結(jié)合。我從未太偏離相對(duì)直接易懂的代數(shù)，并且希望本書能成為有價(jià)值的學(xué)習(xí)資料。

如果沒有大量好心人在時(shí)間、資源以及友善的言辭等方面的幫助，就不可能有本書以及大部分LibTom項(xiàng)目現(xiàn)在的這個(gè)樣子。編寫一部長(zhǎng)書（以及源代碼）是一個(gè)累人且冗長(zhǎng)的過程。目前，LibTom已面世5年了，它有成千上萬(wàn)的使用者，包含了10萬(wàn)多行源代碼、TEX和其他資料。Mads Rassmussen和Greg Rose從一開始就鼓勵(lì)我完成這項(xiàng)工作，有時(shí)候別人的認(rèn)可能極大提升我繼續(xù)完成該項(xiàng)目的勇氣。當(dāng)然，我的父母也給了我很大幫助，在2003年的數(shù)月里為我提供食宿。

Greg和Mads是該項(xiàng)目早期階段的重要支持者。2003年8月發(fā)表的本文初稿是幾個(gè)月專職工作的結(jié)晶。長(zhǎng)時(shí)間的工作，以及還需要去學(xué)校讀書持續(xù)不斷地消耗了我的能量，如果沒有他們的支持，我不可能堅(jiān)持下去。

當(dāng)然如果沒有各種LibTom項(xiàng)目的成功，也就沒有這本書。它們的成功不僅僅是我努力工作的結(jié)果，還包含了其他成百上千人的貢獻(xiàn)。有Colin Percival、Sky Schultz、Wayne Scott、J Harper、Dan Kaminsky、Lance James、Simon Johnson、Greg Rose、Clay Culver、Jochen Katz、Zhi Chen、Zed Shaw、Andrew Mann、Matt Johnston、Steven Dake、Richard Amacker、Stefan Arentz、Richard Outerbridge、Martin Carpenter、Craig Schlenter、John Kuhns、Bruce Guenter、Adam Miller、Wesley Shields、John Dirk、Jean–Luc Cooke、Michael Heyman、Nelson Bolyard、Jim Wigginton、Don Porter、Kevin Kenny、Peter LaDow、Neal Hamilton、David Hulton、Paul Schmidt、Wolfgang Ehrhardt、Johan Lindt、Henrik Goldman、Alex Polushin、Martin Marcel、Brian Gladman、Benjamin Goldberg、Tom Wu和Pekka Riikonen在項(xiàng)目開發(fā)的各個(gè)階段花費(fèi)了寶貴的時(shí)間，貢獻(xiàn)了很多想法、更新、補(bǔ)丁，或者是鼓勵(lì)。我要感謝這些年我認(rèn)識(shí)的很多朋友，感謝他們?yōu)槲規(guī)�來的美好時(shí)光以及鼓勵(lì)。我希望通過本項(xiàng)目向他們表達(dá)敬意。

感謝Syngress出版社的編輯們，他們?cè)诙潭痰囊恢軆?nèi)審閱了300多頁(yè)的稿子，并且糾正了很多問題。我還要感謝我未曾提到的很多朋友，他們總能給我鼓勵(lì)，并且能為我?guī)�來歡樂。感謝我的朋友J Harper、Zed Shaw和Simon Johnson，他們?cè)谖医桓逯�前�?duì)本書進(jìn)行了審閱。感謝Secure Science Corporation的Lance James以及Elliptic Semiconductor的全體同仁們，他們?yōu)槲姨峁┝舜罅康暮笃陂_發(fā)時(shí)間，把我送到了Toorcon，并且給我介紹了很多現(xiàn)在我已經(jīng)認(rèn)識(shí)的人。

開放源代碼、開放學(xué)術(shù)、開放思想。

Tom St Denis

多倫多，加拿大

2006年5月

前言
第1章 引言 1
1.1 多精度算術(shù) 1
1.1.1 什么是多精度算術(shù) 1
1.1.2 為什么需要多精度算術(shù) 1
1.1.3 多精度算術(shù)的優(yōu)勢(shì) 2
1.2 本書目的 3
1.3 討論和表示法 4
1.3.1 表示法 4
1.3.2 精度表示法 4
1.3.3 算法輸入和輸出 5
1.3.4 數(shù)學(xué)表達(dá)式 5
1.3.5 算法的效率 5
1.4 練習(xí) 6
1.5 LibTomMath簡(jiǎn)介 7
1.5.1 什么是LibTomMath 7
1.5.2 LibTomMath的目標(biāo) 7
1.6 為什么選擇LibTomMath 8
1.6.1 代碼基 8
1.6.2 API簡(jiǎn)單易懂 8
1.6.3 優(yōu)化 9
1.6.4 可移植性和穩(wěn)定性 9
1.6.5 選擇 10
第2章 入門 11
2.1 庫(kù)的基本知識(shí) 11
2.2 什么是多精度整數(shù) 12
2.3 參數(shù)傳遞 13
2.4 返回值 14
2.5 初始化和清除 15
2.5.1 初始化mp_int 15
2.5.2 清除mp_int 17
2.6 維護(hù)算法 19
2.6.1 增加mp_int的精度 19
2.6.2 初始化可變精度的mp_ints 21
2.6.3 多個(gè)整數(shù)的初始化和清除 23
2.6.4 壓縮多余位 24
練習(xí) 26
第3章 基本操作 27
3.1 簡(jiǎn)介 27
3.2 為mp_int結(jié)構(gòu)賦值 27
3.2.1 拷貝一個(gè)mp_int 27
3.2.2 克隆 30
3.3 將整數(shù)清零 31
3.4 符號(hào)操作 32
3.4.1 絕對(duì)值 32
3.4.2 整數(shù)取反 33
3.5 小常量 34
3.5.1 設(shè)置小常量 34
3.5.2 設(shè)置大常量 35
3.6 比較 37
3.6.1 無符號(hào)數(shù)比較 37
3.6.2 有符號(hào)數(shù)比較 39
練習(xí) 40
第4章 基本算法 41
4.1 簡(jiǎn)介 41
4.2 加法和減法 41
4.2.1 低級(jí)加法 42
4.2.2 低級(jí)減法 45
4.2.3 高級(jí)加法 49
4.2.4 高級(jí)減法 51
4.3 比特和數(shù)字移位 53
4.3.1 乘以2 54
4.3.2 除以2 56
4.4 多項(xiàng)式基運(yùn)算 58
4.4.1 乘以x 59
4.4.2 除以x 61
4.5 2的冪 63
4.5.1 乘以2的冪 63
4.5.2 除以2的冪 66
4.5.3 除以2的冪的余數(shù) 68
練習(xí) 70
第5章 乘法與平方 72
5.1 乘法器 72
5.2 乘法 72
5.2.1 基線乘法 72
5.2.2 使用Comba方法的快速乘法 77
5.2.3 更快的乘法 82
5.2.4 多項(xiàng)式基乘法 84
5.2.5 Karatsuba乘法 86
5.2.6 Toom-Cook 3-Way乘法 92
5.2.7 有符號(hào)乘法 100
5.3 平方 102
5.3.1 基線平方算法 102
5.3.2 使用Comba方法的更快速平方 105
5.3.3 更快的平方 109
5.3.4 多項(xiàng)式基平方 109
5.3.5 Karatsuba平方 109
5.3.6 Toom-Cook平方 114
5.3.7 高級(jí)平方 114
練習(xí) 116
第6章 模縮減 117
6.1 模縮減的基礎(chǔ)知識(shí) 117
6.2 Barrett縮減 117
6.2.1 定點(diǎn)算法 118
6.2.2 選擇小數(shù)點(diǎn) 119
6.2.3 對(duì)商進(jìn)行縮減 120
6.2.4 對(duì)余數(shù)進(jìn)行縮減 120
6.2.5 Barrett算法 121
6.2.6 Barrett設(shè)置算法 124
6.3 Montgomery縮減 125
6.3.1 基于數(shù)位的Montgomery縮減 127
6.3.2 基線Montgomery縮減 128
6.3.3 較快的“Comba”Montgomery縮減 132
6.3.4 Montgomery設(shè)置 137
6.4 縮減基算法 139
6.4.1 選擇模數(shù) 141
6.4.2 k的選擇 141
6.4.3 受限的縮減基縮減 141
6.4.4 未受限的縮減基縮減 146
6.5 算法比較 150
練習(xí) 151
第7章 冪乘 152
7.1 冪乘基礎(chǔ) 152
7.2 k-ary冪乘 155
7.2.1 k的最優(yōu)值 156
7.2.2 滑動(dòng)窗冪乘 156
7.3 模冪乘 158
7.4 快速計(jì)算2的冪 170
練習(xí) 171
第8章 較高級(jí)算法 172
8.1 有余數(shù)的整數(shù)除法 172
8.1.1 商估計(jì) 173
8.1.2 歸一化整數(shù) 174
8.1.3 以b為基的帶余數(shù)的除法 174
8.2 單數(shù)位幫助算法 183
8.2.1 單數(shù)位加法和減法 183
8.2.2 單數(shù)位乘法 186
8.2.3 單數(shù)位除法 188
8.2.4 單數(shù)位求根 191
8.3 隨機(jī)數(shù)生成 195
8.4 格式化表示形式 197
8.4.1 讀取以n為基的輸入 197
8.4.2 生成以n為基的輸出 200
第9章 數(shù)論算法 203
9.1 最大公約數(shù) 203
9.2 最小公倍數(shù) 208
9.3 Jacobi符號(hào)計(jì)算 210
9.4 模逆 216
9.5 素性測(cè)試 221
9.5.1 試除法 222
9.5.2 Fermat測(cè)試 225
9.5.3 Miller-Rabin測(cè)試 226
練習(xí) 229
參考文獻(xiàn) 230大數(shù)運(yùn)算是加密和安全領(lǐng)域必不可少的一部分，要想實(shí)現(xiàn)它，既需要相應(yīng)的數(shù)學(xué)理論知識(shí)，又需要一定的編程技巧。對(duì)于每一個(gè)初學(xué)者，要想掌握它，必定要花費(fèi)大量時(shí)間查閱數(shù)學(xué)書本和C語(yǔ)言教程（也可能是別的語(yǔ)言）。
本書作者為了方便初學(xué)者學(xué)習(xí)及業(yè)內(nèi)人士使用，開發(fā)了一個(gè)免費(fèi)的大數(shù)運(yùn)算庫(kù)，即LibTomMath項(xiàng)目。本書結(jié)合LibTomMath庫(kù)，由淺入深，對(duì)各種大數(shù)運(yùn)算的算法進(jìn)行了闡述。對(duì)每一種運(yùn)算，一般都列出多種算法，并對(duì)其性能進(jìn)行比較。
本書適合于對(duì)算法、IT安全、加密領(lǐng)域感興趣的讀者閱讀。

1. 信息技術(shù)基礎(chǔ)（麒麟操作系統(tǒng)+WPS Office） [主編　芮雪　蔣莉　王亮亮]
2. Office高級(jí)應(yīng)用項(xiàng)目式教程（第2版） [主編 李觀金 張倩文 黎夏克 ]
3. 巧用翻譯學(xué)英語(yǔ)：英漢互譯500例 [王學(xué)文 著]
4. 高等教育多維評(píng)價(jià)體系構(gòu)建與高質(zhì)量發(fā)展研究 [張妍 著]
5. 系統(tǒng)規(guī)劃與管理師章節(jié)習(xí)題與考點(diǎn)特訓(xùn)（第二版） [主編 薛大龍]
6. 計(jì)算機(jī)操作系統(tǒng)實(shí)踐指導(dǎo)（openEuler版） [主編 秦光 曾陳萍 岳付強(qiáng)]
7. 信息系統(tǒng)管理工程師真題及模考卷精析（適用機(jī)考） [主 編 薛大龍 程 剛 上官緒]
8. 航海類院校體育教育教學(xué)研究 [張利超 李寧 著]
9. 新時(shí)代背景下我國(guó)職業(yè)教育產(chǎn)教融合長(zhǎng)效機(jī)制建設(shè)研究 [王玉賢 著]
10. 電路分析 [主編 李飛 毛先柏]
11. 信息系統(tǒng)管理工程師（適用第2版大綱）一站通關(guān) [指尖瘋　編著]
12. 傳統(tǒng)山水畫論解讀與實(shí)踐 [陳鈉 著]
13. 網(wǎng)絡(luò)工程師備考一本通（適配第6版考綱） [夏杰 編著]
14. 陳孝云的職教理想與情懷 [祝吉太 江傳瑞 張義廷 著]
15. 地方本科院校電子信息學(xué)科課程思政案例集 [王甫]
16. Excel數(shù)據(jù)處理與分析（第二版） [主編 張志明 鄒 蕾]
17. 網(wǎng)絡(luò)工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
18. 倉(cāng)儲(chǔ)管理實(shí)務(wù)（第二版） [周寧武 編著]
19. 基于AE與C#的地理信息系統(tǒng)二次開發(fā) [李小根 賈艷昌 喬翠平 姜彤 ]
20. 2023年長(zhǎng)沙市文化和旅游業(yè)發(fā)展報(bào)告 [主編 陳莉]
21. 舞臺(tái)化妝造型設(shè)計(jì) [主編 劉思彤 張 濤 張憶雨]
22. 產(chǎn)教融合視角高校體育專業(yè)實(shí)踐教學(xué)體系構(gòu)建研究 [楊柳青 葉華兵 著]
23. 知識(shí)圖譜及應(yīng)用案例 [張善文 黃文準(zhǔn) 于長(zhǎng)青 陳明淑]
24. Python程序設(shè)計(jì)案例教程（微課版） [主編　石利平　田輝平　余以勝]
25. 皓月繁星：青少年兒童心理成長(zhǎng)手冊(cè) [主　編　林贊歌 副主編　杜志南]
26. 材料力學(xué) [章寶華 趙新勝 徐斌]
27. 系統(tǒng)集成項(xiàng)目管理工程師考試32小時(shí)通關(guān)（第3版） [主編　薛大龍 副主編　上官緒陽(yáng)]
28. 軟考論文高分特訓(xùn)與范文10篇——系統(tǒng)分析師（第二版） [薛大龍 鄒月平 施游]
29. 黃河海勃灣水利樞紐防凌安全運(yùn)行 [王戰(zhàn)領(lǐng) 王叢發(fā) 范瑜彬 著]
30. 大學(xué)生心理健康教育 [方雄 著]