第1章 初等数论 1
1.1导言 1
1.1.1数论概述 1
1.1.2数论的应用 11
1.1.3代数初步 12
1.2可除性理论 18
1.2.1可除性的基本概念及性质 18
1.2.2算术基本定理 23
1.2.3梅森素数与费马数 27
1.2.4欧几里得算法 35
1.2.5连分数 38
1.3丢番图方程 45
1.3.1丢番图方程的基本概念 45
1.3.2线性丢番图方程 46
1.3.3Pell方程 49
1.4算术函数 56
1.4.1可积函数 56
1.4.2函数τ（n）、σ（n）和s（n） 58
1.4.3完全数、亲和数与多亲数 61
1.4.4函数φ（n）、λ（n）和μ（n） 69
1.5素数分布 74
1.5.1素数分布函数π（x） 74
1.5.2用x/1nx逼近π（x） 76
1.5.3用Li（x）逼近π（x） 81
1.5.4黎曼ζ-函数ζ（s） 83
1.5.5第n个素数 90
1.5.6孪生素数分布 92
1.5.7素数项算术级数 95
1.6同余理论 96
1.6.1同余的基本概念与性质 96
1.6.2模运算 101
1.6.3线性同余方程 105
1.6.4中国剩余定理 111
1.6.5高阶同余方程 114
1.6.6勒让德和雅可比符号 119
1.6.7阶和原根 129
1.6.8指数和k次剩余 134
1.7椭圆曲线的算术理论 137
1.7.1椭圆曲线的基本概念 138
1.7.2椭圆曲线的几何复合定律 139
1.7.3椭圆曲线的代数计算定律 140
1.7.4椭圆曲线上的群定律 144
1.7.5椭圆曲线上点的个数 144
1.8小结 146
第2章 计算数论／算法数论 148
2.1简介 148
2.1.1计算／算法数论概述 148
2.1.2计算可行性 151
2.1.3计算复杂性 154
2.1.4数论算法的复杂性 160
2.1.5快速模指数算法 165
2.1.6椭圆曲线上的快速群运算 167
2.2素性检测算法 171
2.2.1确定性的严格素性检测 172
2.2.2费马的拟素性检测 174
2.2.3强拟素性检测 176
2.2.4卢卡斯拟素性检测 181
2.2.5椭圆曲线检测 187
2.2.6关于素性检测历史的小结 189
2.3整数因子分解算法 191
2.3.1整数因子分解的复杂性理论 192
2.3.2试除法和费马方法 195
2.3.3勒让德同余 197
2.3.4连分数法 199
2.3.5二次筛法和数域筛法 202
2.3.6Pollard的“rho”方法和“p—1”方法 205
2.3.7Lenstra的椭圆曲线方法 211
2.4离散对数问题的算法 213
2.4.1Shanks的小步-大步算法 214
2.4.2Silver-Pohlig-Hellman算法 217
2.4.3离散对数的指数演算法 220
2.4.4椭圆曲线离散对数问题的算法 222
2.4.5求根问题的算法 226
2.5量子数论算法 228
2.5.1量子信息和计算 228
2.5.2量子可计算性和复杂性 232
2.5.3整数因子分解的量子算法 233
2.5.4离散对数的量子算法 237
2.6数论中的各式算法 238
2.6.1计算π（x）的算法 239
2.6.2生成亲和数的算法 243
2.6.3验证哥德巴赫猜想的算法 245
2.6.4寻找奇完全数的算法 248
2.7小结 249
第3章 计算／密码学中的应用数论 251
3.1研究应用数论的意义 251
3.2计算机系统设计 252
3.2.1剩余系中数的表示 253
3.2.2剩余数系中的快速计算 255
3.2.3剩余计算机 259
3.2.4余运算 260
3.2.5哈希函数 264
3.2.6检错和纠错方法 266
3.2.7随机数的生成 270
3.3密码学和信息安全 275
3.3.1介绍 276
3.3.2私钥密码学 277
3.3.3数据／高级加密标准 286
3.3.4公钥密码学 289
3.3.5基于离散对数的密码体制 293
3.3.6公钥密码体制 296
3.3.7二次剩余密码体制 308
3.3.8椭圆曲线公钥密码体制 313
3.3.9数字签名 318
3.3.10数字签名标准 324
3.3.11数据库安全 326
3.3.12秘密共享 330
3.3.13因特网／环球网安全和电子商务 333
3.3.14隐写术 337
3.3.15量子密码学 338
3.4小结 339
参考文献 341