本書的誕生是我人生的一個有趣的經歷。那段時期我從一個涉世未深的年輕人成長為一個周游列國、結識了無數新朋友和同事的軟件開發者。這一切開始于2001年12月，大約5年前，我開始了一個后來名為LibTomCrypt的項目，該項目被業內廣泛使用。

我從事LibTomCrypt項目的最初目的是想把我的精力集中在某些有建設性的事情上，同時學習一些新技能。從事該項目的第一年，我學會了如何組織產品、歸檔文件，以及如何進行后續的支持和維護。大約在2002年冬季，我開始尋求另一個項目以打發時間。由于意識到LibTomCrypt缺乏數學支持，于是著手開發一個新的數學庫。

這樣LibTomMath項目就誕生了。它最初只是現有項目的補丁集，很快就發展為一個單獨的項目。從頭編寫這個數學庫是生產一個穩定和獨立的產品的基本原則。我還學會了哪些算法可用來進行如模冪等這樣的運算。這個庫僅經過幾個月的開發就非常穩定和可靠，并且立即投入使用。

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

當我向別人提起LibTom項目（共有6個）并且告訴他們我準備公開發布時，他們都覺得很詫異。他們問我為什么這么做，尤其是為什么還要繼續免費進行下去。我能做出的最好的解釋就是 “因為我能夠”。這對于成人間的對話來說有些奇怪，并且過于簡單。我通常進一步解釋為“我有這個能力，并且我愿意”，這也許更能說明問題。我是第一個承認我所做的并無特殊之處的人，也許還有其他人也這么看，那么我們就可以組成一個令人自豪的小團體。我的LibTom項目是我正在以工具和知識的形式回饋社會、能給他人帶來幫助的東西。

我編寫本書是因為它能進一步實現我的學術開放的目標。LibTomMath的源代碼本身很容易領悟和學習。但有很多時候，純粹的C代碼不能恰當地解釋本書中的算法。本書首先解釋該庫的基礎，然后再介紹更復雜的算法。偽代碼和源代碼的同時使用提供了全世界計算機專業學生更容易接受的“理論”和“實踐”的雙重結合。我從未太偏離相對直接易懂的代數，并且希望本書能成為有價值的學習資料。

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

Greg和Mads是該項目早期階段的重要支持者。2003年8月發表的本文初稿是幾個月專職工作的結晶。長時間的工作，以及還需要去學校讀書持續不斷地消耗了我的能量，如果沒有他們的支持，我不可能堅持下去。

當然如果沒有各種LibTom項目的成功，也就沒有這本書。它們的成功不僅僅是我努力工作的結果，還包含了其他成百上千人的貢獻。有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在項目開發的各個階段花費了寶貴的時間，貢獻了很多想法、更新、補丁，或者是鼓勵。我要感謝這些年我認識的很多朋友，感謝他們為我帶來的美好時光以及鼓勵。我希望通過本項目向他們表達敬意。

感謝Syngress出版社的編輯們，他們在短短的一周內審閱了300多頁的稿子，并且糾正了很多問題。我還要感謝我未曾提到的很多朋友，他們總能給我鼓勵，并且能為我帶來歡樂。感謝我的朋友J Harper、Zed Shaw和Simon Johnson，他們在我交稿之前對本書進行了審閱。感謝Secure Science Corporation的Lance James以及Elliptic Semiconductor的全體同仁們，他們為我提供了大量的后期開發時間，把我送到了Toorcon，并且給我介紹了很多現在我已經認識的人。

開放源代碼、開放學術、開放思想。

Tom St Denis

多倫多，加拿大

2006年5月

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

1. 輸水管線工程風險管理 [張勇 黨亥生 著]
2. 民用航空飛機標準線路施工 [主編　王志敏　陳明]
3. 不息的水脈—大運河講談錄 [趙珩　著]
4. 實用運籌學 [主編　邢育紅　于晉臣]
5. 三峽梯級電站水資源決策支持系統研究與開發 [姚華明 潘紅忠 湯正]
6. 海南黎族民俗文化鑒賞 [龐國華　著]
7. 石墨烯在太赫茲及中紅外頻段電磁器件設計中的應用 [李艷秀 莊華偉 著]
8. 電子技術（第二版） [主編 覃愛娜 李飛]
9. 辦公自動化高級應用 [陳萍 朱曉玉]
10. 信息處理技術員考試32小時通關 [薛大龍]
11. 電子產品設計案例教程（微課版）—基于嘉立創EDA（專業版） [王靜 莫志宏 陳學昌 丁紅]
12. C程序設計實踐教程 [劉衛國]
13. C程序設計（慕課版） [劉衛國]
14. Web技術開發教程（基于.NET開源MVC框架） [王合闖 韓紅玲 王青正 陳海蕊]
15. 商務英語翻譯教程（筆譯）（第四版） [主編 王軍平]
16. 智慧零售技術與應用 [洪旭 著]
17. 建設工程法規實務 [主編 余瀅]
18. 商務秘書理論與實務（第三版） [主編 張同欽]
19. 程序設計基礎實踐教程（C/C++語言版） [張桂芬 葛麗娜]
20. C++案例項目精講 [主編 楊國興]
21. 勞動爭議處理實務 [主編 王秀卿 羅靜]
22. 工程數學 [主編 郭立娟 王海]
23. 語音識別理論與實踐 [主編　莫宏偉]
24. 信息系統項目管理師章節習題與考點特訓（第二版） [主編 薛大龍]
25. 武術基礎教程 [主編 李代勇 謝志民]
26. 計算機網絡實訓教程 [主編 張浩軍 趙玉娟]
27. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
28. HCIA-Datacom認證題庫分類精講 [主 編 韓立剛]
29. SwiftUI完全開發 [李智威 著]
30. 網絡規劃設計師備考一本通 [夏杰 編著]