BigNum Math：加密多精度算法的理论与实现

本书的诞生是我人生的一个有趣的经历。那段时期我从一个涉世未深的年轻人成长为一个周游列国、结识了无数新朋友和同事的软件开发者。这一切开始于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章 模缩减 117
6.1 模缩减的基础知识 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. 网络规划设计师备考一本通 [夏杰 编著]