第 1章整数的可除性 .................................................................................................. 1
1.1整除的概念、欧几里得除法 ............................................................................. 1
1.1.1整除的概念 ........................................................................................... 1
1.1.2 Eratoshenes筛法 ................................................................................... 4
1.1.3欧几里得除法 ——最小非负余数 .......................................................... 6
1.1.4素数的平凡判别 .................................................................................... 7
1.1.5欧几里得除法 ——一般余数 ................................................................. 7
1.2整数的表示 ..................................................................................................... 9
1.2.1 b进制 ................................................................................................... 9
1.2.2计算复杂性 ..........................................................................................15
1.3最大公因数与广义欧几里得除法 .....................................................................20
1.3.1最大公因数 ..........................................................................................20
1.3.2广义欧几里得除法及计算最大公因数 ....................................................22
1.3.3 B′ezout等式 .........................................................................................24
1.3.4 B′ezout等式的证明 ...............................................................................27
1.3.5最大公因数的进一步性质 .....................................................................33
1.3.6多个整数的最大公因数及计算 ..............................................................36
1.3.7形为 2a . 1的整数及其最大公因数 ......................................................37
1.4整除的进一步性质及最小公倍数 .....................................................................37
1.4.1整除的进一步性质 ................................................................................37
1.4.2最小公倍数 ..........................................................................................38
1.4.3最小公倍数与最大公因数 .....................................................................39
1.4.4多个整数的最小公倍数 .........................................................................40
1.5整数分解 ........................................................................................................41
1.6素数的算术基本定理 ......................................................................................42
1.6.1算术基本定理 .......................................................................................42
1.6.2算术基本定理的应用 ............................................................................44
1.7素数定理 ........................................................................................................47
1.8习题 ...............................................................................................................48
第 2章同余 ..............................................................................................................53
2.1同余的概念及基本性质 ...................................................................................53
2.1.1同余的概念 ..........................................................................................53
2.1.2同余的判断 ..........................................................................................54
2.1.3同余的性质 ..........................................................................................59
2.2剩余类及完全剩余系 ......................................................................................62
2.2.1剩余类与剩余 .......................................................................................62
vi目录
2.2.2完全剩余系 ..........................................................................................64
2.2.3两个模的完全剩余系 ............................................................................65
2.2.4多个模的完全剩余系 ............................................................................66
2.3简化剩余系与欧拉函数 ...................................................................................67
2.3.1欧拉函数 ..............................................................................................67
2.3.2简化剩余类与简化剩余系 .....................................................................68
2.3.3两个模的简化剩余系 ............................................................................72
2.3.4欧拉函数的性质 ...................................................................................73
2.4欧拉定理、费马小定理和 Wilson定理 .............................................................76
2.4.1欧拉定理 ..............................................................................................76
2.4.2费马小定理 ..........................................................................................78
2.4.3 Wilson定理 .........................................................................................79
2.5模重复平方计算法 ..........................................................................................80
2.6习题 ...............................................................................................................88
第 3章同余式 ..........................................................................................................91
3.1基本概念及一次同余式 ...................................................................................91
3.1.1同余式的基本概念 ................................................................................91
3.1.2一次同余式 ..........................................................................................92
3.2中国剩余定理 .................................................................................................95
3.2.1中国剩余定理:“物不知数”与韩信点兵 ...............................................95
3.2.2两个方程的中国剩余定理 .....................................................................98
3.2.3中国剩余定理之构造证明 .....................................................................99
3.2.4中国剩余定理之递归证明 ................................................................... 101
3.2.5中国剩余定理之应用 ——算法优化 ................................................... 104
3.3高次同余式的解数及解法 ............................................................................. 109
3.3.1高次同余式的解数 .............................................................................. 109
3.3.2高次同余式的提升 .............................................................................. 111
3.3.3高次同余式的提升 ——具体应用 ....................................................... 113
3.4素数模的同余式 ........................................................................................... 115
3.4.1素数模的多项式欧几里得除法 ............................................................ 115
3.4.2素数模的同余式的简化 ....................................................................... 116
3.4.3素数模的同余式的因式分解 ................................................................ 117
3.4.4素数模的同余式的解数估计 ................................................................ 118
3.5习题 ............................................................................................................. 121
第 4章二次同余式与平方剩余 ................................................................................ 125
4.1一般二次同余式 ........................................................................................... 125
4.2模为奇素数的平方剩余与平方非剩余 ............................................................ 128
4.3勒让得符号 .................................................................................................. 131
目录 vii
4.3.1勒让得符号之运算性质 ....................................................................... 131
4.3.2高斯引理 ............................................................................................ 134
4.4二次互反律 .................................................................................................. 137
4.5雅可比符号 .................................................................................................. 143
4.6模平方根 ...................................................................................................... 146
4.6.1模 p平方根 ........................................................................................ 146
4.6.2模 p平方根 ........................................................................................ 149
4.6.3模 m平方根 ...................................................................................... 155
2
4.7 x2 + y= p .................................................................................................... 159
4.8习题 ............................................................................................................. 163
第 5章原根与指标 ................................................................................................. 166
5.1指数及其基本性质 ........................................................................................ 166
5.1.1指数 ................................................................................................... 166
5.1.2指数的基本性质 ................................................................................. 168
5.1.3大指数的构造 ..................................................................................... 173
5.2原根 ............................................................................................................. 178
5.2.1模 p原根 ........................................................................................... 178
5.2.2模 pα原根 ......................................................................................... 181
5.2.3模 2α指数 ......................................................................................... 184
5.2.4模 m原根 .......................................................................................... 186
5.3指标及 n次同余式 ....................................................................................... 191
5.3.1指标 ................................................................................................... 191
5.3.2 n次同余式 ......................................................................................... 193
5.4习题 ............................................................................................................. 196
第 6章素性检验 ..................................................................................................... 198
6.1伪素数 ......................................................................................................... 198
6.1.1伪素数 Fermat素性检验 .................................................................... 198
6.1.2无穷多伪素数 ..................................................................................... 201
6.1.3平方因子的判别 ................................................................................. 202
6.1.4 Carmicheal数 ..................................................................................... 203
6.2 Euler伪素数 ................................................................................................ 204
6.2.1 Euler伪素数、Solovay-Stassen素性检验 ............................................. 204
6.2.2无穷多 Euler伪素数 ........................................................................... 208
6.3强伪素数 ...................................................................................................... 209
6.3.1强伪素数、Miller-Rabin素性检验 ....................................................... 209
6.3.2无穷多强伪素数 ................................................................................. 210
6.4习题 ............................................................................................................. 211
viii目录
第 7章连分数 ........................................................................................................ 212
7.1简单连分数 .................................................................................................. 212
7.1.1简单连分数构造 ................................................................................. 212
7.1.2简单连分数的渐近分数 ....................................................................... 214
7.1.3重要常数 e, π, γ的简单连分数 ......................................................... 216
7.2连分数 ......................................................................................................... 218
7.2.1基本概念及性质 ................................................................................. 218
7.2.2连分数的渐近分数 .............................................................................. 221
7.3简单连分数的进一步性质 ............................................................................. 224
7.4最佳逼近 ...................................................................................................... 225
7.5循环连分数 .................................................................................................. 227
7.6 √ n与因数分解 ............................................................................................ 227
7.7习题 ............................................................................................................. 230
第 8章群 ............................................................................................................... 232
8.1群 ................................................................................................................ 232
8.1.1基本定义 ............................................................................................ 232
8.1.2子群 ................................................................................................... 241
8.2正规子群和商群 ........................................................................................... 243
8.2.1陪集的拉格朗日定理 .......................................................................... 243
8.2.2陪集的进一步性质 .............................................................................. 245
8.2.3正规子群和商群 ................................................................................. 247
8.3同态和同构 .................................................................................................. 248
8.3.1基本概念 ............................................................................................ 248
8.3.2同态分解定理 ..................................................................................... 250
8.3.3同态分解定理的进一步性质 ................................................................ 251
8.4习题 ............................................................................................................. 253
第 9章群的结构 ..................................................................................................... 255
9.1循环群 ......................................................................................................... 255
9.1.1循环群 ............................................................................................... 255
9.1.2循环子群的构造 ................................................................................. 255
9.2有限生成交换群 ........................................................................................... 259
9.3置换群 ......................................................................................................... 261
9.4习题 ............................................................................................................. 266
第 10章环与理想 ................................................................................................... 267
10.1环 ............................................................................................................... 267
10.1.1基本定义 ......................................................................................... 267
10.1.2零因子环 ......................................................................................... 269
目录
10.1.3整环及域 ......................................................................................... 270
10.1.4交换环上的整除 .............................................................................. 271
10.2同态 ........................................................................................................... 272
10.3特征及素域 ................................................................................................. 272
10.4分式域 ........................................................................................................ 273
10.5理想和商环 ................................................................................................. 276
10.5.1理想 ................................................................................................ 276
10.5.2商环 ................................................................................................ 281
10.5.3环同态分解定理 .............................................................................. 282
10.6素理想 ........................................................................................................ 283
10.7习题 ........................................................................................................... 285
第 11章多项式环 ................................................................................................... 287
11.1多项式整环 ................................................................................................. 287
11.2多项式整除与不可约多项式 ........................................................................ 288
11.3多项式欧几里得除法 ................................................................................... 290
11.4多项式同余 ................................................................................................. 296
11.5本原多项式 ................................................................................................. 300
11.6多项式理想 ................................................................................................. 303
11.7多项式结式与判别式 ................................................................................... 303
11.8习题 ........................................................................................................... 307
第 12章域和 Galois理论 ...................................................................................... 309
12.1域的扩张 .................................................................................................... 309
12.1.1域的有限扩张 .................................................................................. 309
12.1.2域的代数扩张 .................................................................................. 312
12.2 Galois基本定理 .......................................................................................... 315
12.2.1 K-同构 .......................................................................................... 315
12.2.2 Galois基本定理概述 ....................................................................... 319
12.2.3基本定理之证明 .............................................................................. 323
12.3可分域、代数闭包 ....................................................................................... 324
12.3.1可分域 ............................................................................................ 324
12.3.2代数闭包 ......................................................................................... 324
12.4习题 ........................................................................................................... 325
第 13章域的结构 ................................................................................................... 327
13.1超越基 ........................................................................................................ 327
13.2有限域的构造 ............................................................................................. 327
13.3有限域的 Galois群 ..................................................................................... 329
13.3.1有限域的 Frobenius映射 ................................................................. 329
x目录
13.3.2有限域的 Galois群概述 ................................................................... 334
13.4正规基 ........................................................................................................ 335
13.5习题 ........................................................................................................... 338
第 14章椭圆曲线 ................................................................................................... 340
14.1椭圆曲线基本概念 ...................................................................................... 340
14.2加法原理 .................................................................................................... 342
14.2.1实数域 R上椭圆曲线 ..................................................................... 345
14.2.2素域 Fp (p> 3)上的椭圆曲线 E ...................................................... 347
14.2.3域 F2n
(n》 1)上的椭圆曲线 E, j(E)= 0 ......................................... 355
14.3有限域上的椭圆曲线的阶 ............................................................................ 358
14.4重复倍加算法 ............................................................................................. 359
14.5习题 ........................................................................................................... 361
第 15章 AKS素性检验 .......................................................................................... 362
附录 A三个数学难题 .............................................................................................. 364
附录 B周期序列 ..................................................................................................... 365
附录 C前 1280个素数及其原根表 .......................................................................... 367
附录 D F359 .............................................................................................................. 375
D.1域 F359中生成元 g =7的幂指表:由 k得到 h = gk ...................................... 375
D.2域 F359中生成元 g =7的指数表:由 h得到 gk = h ...................................... 378
附录 E F28 = F2[x]/(x8 + x4 + x3 + x2 + 1) ................................................................ 380
E.1域中生成元 g = x的幂指表:由 k得到 h = gk ............................................... 380
E.2域中生成元 g = x的指数表:由 h得到 gk = h ............................................... 384
E.3域中生成元 g = x的幂的函数 u2 + u表:由 k得到 h = g2k + gk .................... 388
E.4域中生成元 g = x的广义指数表:由 h得到 g2k + gk = h ............................... 392
附录 F F28 = F2[x]/(x8 + x4 + x3 + x + 1).................................................................. 396
F.1域中生成元 g = x +1的幂指表:由 k得到 h = gk ......................................... 396
F.2域中生成元 g = x +1的指数表:由 h得到 gk = h ......................................... 400
F.3域中生成元 g = x +1的幂的函数 u2 + u表:由 k得到 h = g2k + gk .............. 404
F.4域中生成元 g = x +1的广义指数表:由 h得到 g2k + gk = h.......................... 408
索引 ........................................................................................................................... 412
参考文献 .................................................................................................................... 416
