目录
第1 章整数的可除性............................................................................. 1
1.1 整除的概念、欧几里得除法........................................................... 1
1.1.1 整除的概念...................................................................... 1
1.1.2 Eratosthenes 筛法.............................................................. 4
1.1.3 欧几里得除法——最小非负余数............................................ 6
1.1.4 素数的平凡判别................................................................ 7
1.1.5 欧几里得除法——一般余数.................................................. 7
1.2 整数的表示................................................................................ 8
1.2.1 b 进制............................................................................. 8
1.2.2 计算复杂性...................................................................... 15
1.3 最大公因数与广义欧几里得除法..................................................... 19
1.3.1 最大公因数...................................................................... 19
1.3.2 广义欧几里得除法及计算最大公因数...................................... 21
1.3.3 Bézout 等式..................................................................... 23
1.3.4 Bézout 等式的证明............................................................ 26
1.3.5 最大公因数的进一步性质..................................................... 31
1.3.6 多个整数的最大公因数及计算............................................... 34
1.3.7 形为2a ?? 1 的整数及其最大公因数......................................... 35
1.4 整除的进一步性质及最小公倍数..................................................... 35
1.4.1 整除的进一步性质............................................................. 35
1.4.2 最小公倍数...................................................................... 36
1.4.3 最小公倍数与最大公因数..................................................... 37
1.4.4 多个整数的最小公倍数........................................................ 38
1.5 整数分解................................................................................... 39
1.6 素数的算术基本定理.................................................................... 40
1.6.1 算术基本定理................................................................... 40
信息安全数学基础（第3 版）
1.6.2 算术基本定理的应用........................................................... 41
1.7 素数定理................................................................................... 45
1.8 习题........................................................................................ 46
第2 章同余........................................................................................ 47
2.1 同余的概念及基本性质................................................................. 47
2.1.1 同余的概念...................................................................... 47
2.1.2 同余的判断...................................................................... 48
2.1.3 同余的性质...................................................................... 52
2.2 剩余类及完全剩余系.................................................................... 55
2.2.1 剩余类与剩余................................................................... 55
2.2.2 完全剩余系...................................................................... 57
2.2.3 两个模的完全剩余系........................................................... 58
2.2.4 多个模的完全剩余系........................................................... 60
2.3 简化剩余系与欧拉函数................................................................. 61
2.3.1 欧拉函数......................................................................... 61
2.3.2 简化剩余类与简化剩余系..................................................... 61
2.3.3 两个模的简化剩余系........................................................... 65
2.3.4 欧拉函数的性质................................................................ 65
2.4 欧拉定理、费马小定理和Wilson 定理............................................... 68
2.4.1 欧拉定理......................................................................... 68
2.4.2 费马小定理...................................................................... 70
2.4.3 Wilson 定理...................................................................... 71
2.5 模重复平方计算法....................................................................... 72
2.6 习题........................................................................................ 80
第3 章同余式..................................................................................... 81
3.1 基本概念及一次同余式................................................................. 81
3.1.1 同余式的基本概念............................................................. 81
3.1.2 一次同余式...................................................................... 82
3.2 中国剩余定理............................................................................. 85
3.2.1 中国剩余定理: “物不知数”与韩信点兵................................. 85
3.2.2 两个方程的中国剩余定理..................................................... 88
3.2.3 中国剩余定理之构造证明..................................................... 89
3.2.4 中国剩余定理之递归证明..................................................... 90
3.2.5 中国剩余定理之应用——算法优化......................................... 93
VIII
目录
3.3 高次同余式的解数及解法.............................................................. 98
3.3.1 高次同余式的解数............................................................. 98
3.3.2 高次同余式的提升............................................................. 100
3.3.3 高次同余式的提升——具体应用............................................ 102
3.4 素数模的同余式.......................................................................... 104
3.4.1 素数模的多项式欧几里得除法............................................... 104
3.4.2 素数模的同余式的简化........................................................ 105
3.4.3 素数模的同余式的因式分解.................................................. 106
3.4.4 素数模的同余式的解数估计.................................................. 107
3.5 习题........................................................................................ 109
第4 章二次同余式与平方剩余................................................................. 110
4.1 一般二次同余式.......................................................................... 110
4.2 模为奇素数的平方剩余与平方非剩余............................................... 114
4.3 勒让德符号................................................................................ 116
4.3.1 勒让德符号之运算性质........................................................ 116
4.3.2 高斯引理......................................................................... 118
4.4 二次互反律................................................................................ 121
4.5 雅可比符号................................................................................ 127
4.6 模平方根................................................................................... 130
4.6.1 模p = 4k + 3 平方根........................................................... 130
4.6.2 模p 平方根....................................................................... 133
4.6.3 模m平方根...................................................................... 138
4.7 x2 + y2 = p ................................................................................ 142
4.8 习题........................................................................................ 145
第5 章原根与指标................................................................................ 146
5.1 指数及其基本性质....................................................................... 146
5.1.1 指数............................................................................... 146
5.1.2 指数的基本性质................................................................ 148
5.1.3 大指数的构造................................................................... 152
5.2 原根........................................................................................ 157
5.2.1 模p 原根.......................................................................... 157
5.2.2 模pα 原根........................................................................ 160
5.2.3 模2α 指数........................................................................ 162
5.2.4 模m原根......................................................................... 164
IX
信息安全数学基础（第3 版）
5.3 指标及n次同余式....................................................................... 169
5.3.1 指标............................................................................... 169
5.3.2 n次同余式....................................................................... 171
5.4 习题........................................................................................ 174
第6 章素性检验................................................................................... 175
6.1 伪素数...................................................................................... 175
6.1.1 伪素数Fermat 素性检验...................................................... 175
6.1.2 无穷多伪素数................................................................... 178
6.1.3 平方因子的判别................................................................ 179
6.1.4 Carmichael 数................................................................... 180
6.2 Euler 伪素数.............................................................................. 181
6.2.1 Euler 伪素数、Solovay-Stassen 素性检验.................................. 181
6.2.2 无穷多Euler 伪素数............................................................ 184
6.3 强伪素数................................................................................... 185
6.3.1 强伪素数、Miller-Rabin 素性检验.......................................... 185
6.3.2 无穷多强伪素数................................................................ 186
6.4 习题........................................................................................ 187
第7 章连分数..................................................................................... 188
7.1 简单连分数................................................................................ 188
7.1.1 简单连分数构造................................................................ 188
7.1.2 简单连分数的渐近分数........................................................ 190
7.1.3 重要常数e、π、γ 的简单连分数............................................ 192
7.2 连分数简介................................................................................ 194
7.2.1 基本概念及性质................................................................ 194
7.2.2 连分数的渐近分数............................................................. 197
7.3 简单连分数的进一步性质.............................................................. 199
7.4 最佳逼近................................................................................... 200
7.5 循环连分数................................................................................ 202
7.6
p
n与因数分解........................................................................... 203
7.7 习题........................................................................................ 205
第8 章群........................................................................................... 206
8.1 群简介...................................................................................... 206
8.1.1 基本定义......................................................................... 206
8.1.2 子群............................................................................... 214
X
目录
8.2 正规子群和商群.......................................................................... 216
8.2.1 陪集的拉格朗日定理........................................................... 216
8.2.2 陪集的进一步性质............................................................. 219
8.2.3 正规子群和商群................................................................ 220
8.3 同态和同构................................................................................ 221
8.3.1 基本概念......................................................................... 221
8.3.2 同态分解定理................................................................... 223
8.3.3 同态分解定理的进一步性质.................................................. 224
8.4 习题........................................................................................ 226
第9 章群的结构................................................................................... 227
9.1 循环群...................................................................................... 227
9.2 有限生成交换群.......................................................................... 231
9.3 置换群...................................................................................... 232
9.4 习题........................................................................................ 237
第10 章环与理想.................................................................................. 238
10.1 环........................................................................................... 238
10.1.1 基本定义........................................................................ 238
10.1.2 零因子环........................................................................ 240
10.1.3 整环及域........................................................................ 241
10.1.4 交换环上的整除............................................................... 242
10.2 同态........................................................................................ 243
10.3 特征及素域................................................................................ 243
10.4 分式域..................................................................................... 244
10.5 理想和商环................................................................................ 246
10.5.1 理想.............................................................................. 246
10.5.2 商环.............................................................................. 251
10.5.3 环同态分解定理............................................................... 252
10.6 素理想..................................................................................... 253
10.7 习题........................................................................................ 255
第11 章多项式环.................................................................................. 256
11.1 多项式整环................................................................................ 256
11.2 多项式整除与不可约多项式........................................................... 257
11.3 多项式欧几里得除法.................................................................... 259
11.4 多项式同余................................................................................ 264
XI
信息安全数学基础（第3 版）
11.5 本原多项式................................................................................ 268
11.6 多项式理想................................................................................ 271
11.7 多项式结式与判别式.................................................................... 271
11.8 习题........................................................................................ 275
第12 章域和Galois 理论........................................................................ 276
12.1 域的扩张................................................................................... 276
12.1.1 域的有限扩张.................................................................. 276
12.1.2 域的代数扩张.................................................................. 279
12.2 Galois 基本定理.......................................................................... 282
12.2.1 K-同构.......................................................................... 282
12.2.2 Galois 基本定理概述......................................................... 285
12.2.3 基本定理之证明............................................................... 289
12.3 可分域、代数闭包....................................................................... 290
12.3.1 可分域........................................................................... 290
12.3.2 代数闭包........................................................................ 291
12.4 习题........................................................................................ 291
第13 章域的结构.................................................................................. 292
13.1 超越基..................................................................................... 292
13.2 有限域的构造............................................................................. 292
13.3 有限域的Galois 群....................................................................... 295
13.3.1 有限域的Frobenius 映射..................................................... 295
13.3.2 有限域的Galois 群概述...................................................... 299
13.4 正规基..................................................................................... 299
13.5 习题........................................................................................ 303
第14 章椭圆曲线.................................................................................. 304
14.1 椭圆曲线简介............................................................................. 304
14.2 加法原理................................................................................... 307
14.2.1 实数域R 上的椭圆曲线...................................................... 308
14.2.2 素域Fp(p > 3) 上的椭圆曲线E ............................................ 310
14.2.3 域F2n(n ? 1) 上的椭圆曲线E, j(E) 6= 0 ................................ 318
14.3 有限域上的椭圆曲线的阶.............................................................. 321
14.4 重复倍加算法............................................................................. 321
14.5 习题........................................................................................ 323
XII
目录
第15 章AKS 素性检验........................................................................... 324
附录A 三个数学难题............................................................................ 326
附录B 周期序列.................................................................................. 327
附录C 前1280 个素数及其原根表............................................................ 328
附录D F359 ......................................................................................... 329
附录E F28 = F2[x]/(x8 + x4 + x3 + x2 + 1) ................................................ 330
附录F F28 = F2[x]/(x8 + x4 + x3 + x + 1) ................................................. 331
参考文献............................................................................................... 332
