第1章 高精度运算 1
1.1 整数 2
1.1.1 进制转换 2
1.1.2 四则运算 3
1.2 快速乘法 7
1.2.1 一元多项式乘法 7
1.2.2 Karatsuba乘法 9
1.2.3 Toom-Cook乘法 11
1.2.4 FFT乘法 12
第2章 素数判定 18
2.1 Fermat检测 19
2.2 Euler检测 20
2.3 Lehmer N-1型检测 21
2.4 Lucas伪素数检测与N+1型检测 23
2.5 概率性检测方法 27
2.5.1 Solovay-Strassen检测 27
2.5.2 Rabin-Miller检测 28
2.5.3 Baillie-PSW检测 29
第3章 整数因子分解 31
3.1 试除法 31
3.2 Euclid算法 32
3.3 Pollard ρ-1方法 32
3.4 Pollard ρ方法 34
3.5 平方型分解 36
3.6 连分式方法 37
3.7 椭圆曲线方法 38
3.8 二次筛法 43
3.8.1 单个多项式二次筛法 43
3.8.2 多个多项式二次筛法 44
3.9 数域筛法 44
第4章 基础数论算法 45
4.1 快速求幂 45
4.1.1 二进方法 45
4.1.2 m进方法，窗口方法及加法链 47
4.1.3 Montgomery约化 48
4.2 幂次检测 50
4.2.1 整数开方 50
4.2.2 平方检测 50
4.2.3 素数幂检测 51
4.3 最大公因子 52
4.3.1 Euclid算法 53
4.3.2 Lehmer加速算法 53
4.3.3 二进方法 55
4.3.4 扩展Euclid算法 56
4.3.5 dmod与bmod 57
4.3.6 Jebelean-Weber-Sorenson加速算法 58
4.4 Legendre-Jacobi-Kronecker符号 60
4.5 中国剩余定理 64
4.6 连分数展式 65
4.7 素数计数函数π（x） 67
4.7.1 部分筛函数 68
4.7.2 计算P2(x,α) 68
4.7.3 计算φ(x,α) 69
4.7.4 计算S 70
4.7.5 计算S1 70
4.7.6 计算S3 71
4.7.7 计算S2 71
4.7.8 计算V 71
4.7.9 计算V2 72
4.8 第n个素数pn 73
4.9 M？bius函数μ（n）和Euler函数？（n） 74
第5章 数学常数 75
5.1 圆周率 75
5.1.1 级数方法 75
5.1.2 迭代方法 82
5.2 自然对数底 87
5.2.1 级数方法 87
5.3 对数常数 89
5.3.1 级数方法 89
5.3.2 迭代方法 91
5.4 Euler常数 91
5.4.1 级数方法 91
第6章 线性代数 94
6.1 快速矩阵乘法 94
6.1.1 基于向量内积算法的Winograd算法 95
6.1.2 Strassen算法 95
6.2 线性方程组与消元法 97
6.2.1 基于中国剩余定理的消元法 98
6.2.2 Padé逼近与有理函数重建 108
6.2.3 Hensel提升算法 111
6.2.4 数值算法求精确解 113
6.3 Wiedemann算法与黑箱方法 119
6.3.1 概率性算法与预处理步骤概述 119
6.3.2 线性递推列 123
6.3.3 线性方程组的Wiedemann算法 126
第7章 一元多项式求值和插值 130
7.1 求值算法 130
7.2 插值算法 133
第8章 一元多项式的最大公因子 135
8.1 Euclid算法 135
8.2 域上多项式的快速Euclid算法 138
8.3 结式性质及其计算 143
8.3.1 结式 143
8.3.2 Euclid算法计算结式 145
8.4 Z［x］中的模GCD算法 150
8.4.1 Mignotte界 150
8.4.2 大素数模公因子算法 153
8.4.3 小素数模公因子算法 155
8.5 多项式组的概率算法 158
第9章 有限域上多项式因子分解 160
9.1 不同次数因子分解 161
9.1.1 有限域Fp和Fpd 161
9.1.2 不同次因子分解 162
9.2 同次因子分解 164
9.2.1 特征为奇素数的有限域 164
9.2.2 特征为2的有限域 166
9.3 一个完整的因子分解算法及其应用 167
9.4 无平方因子分解 169
9.4.1 特征为零的域上无平方分解 170
9.4.2 特征有限的域上无平方分解 171
9.5 Berlekamp算法 175
9.5.1 Frobenius映射和Berlekamp子代数 175
9.5.2 Berlekamp算法的实现 176
9.6 各算法复杂度比较 178
9.7 不可约性检测和不可约多项式的构造 178
第10章 整系数多项式因子分解 182
10.1 大素数模方法和因子组合算法 183
10.2 Hensel提升理论 187
10.2.1 Hensel单步算法 187
10.2.2 利用因子树进行多因子Hensel提升 192
10.3 应用Hensel提升的Zassenhaus算法 193
10.4 格中短向量理论 196
10.4.1 问题的引入 196
10.4.2 约化基算法 198
10.4.3 约化基算法的细节说明 201
10.5 应用格中短向量的分解算法 203
第11章 多元多项式 207
11.1 多元多项式插值方法 207
11.1.1 稠密插值 208
11.1.2 稀疏插值 208
11.2 Euclid算法和一般模算法 213
11.2.1 概述 213
11.2.2 Fp［x1,x2,…,xn］上最大公因子 214
11.2.3 多元多项式的“Mignotte”界 215
11.2.4 Z［x1,x2,…,xn］上最大公因子 216
11.3 Zippel稀疏插值算法 217
11.3.1 一个具体的例子 218
11.3.2 算法描述 219
11.4 求GCD其他方法 222
11.4.1 启发式算法 222
11.4.2 EZ-GCD 222
11.5 多元多项式因子分解Kronecker算法 222
11.6 利用Hensel提升的因子分解算法 224
11.6.1 概述 224
11.6.2 扩展Zassenhaus算法 224
11.6.3 因子还原 228
11.6.4 预先确定因子的首项系数 229
第12章 一元多项式求根算法 233
12.1 多项式零点模估计 234
12.2 Jenkins-Traub算法 236
12.2.1 算法引入 236
12.2.2 收敛速度和细节说明 240
12.3 Laguerre算法 242
12.4 代数模方程求解 243
12.4.1 Fp中的开平方算法 243
12.4.2 模p代数方程求解 245
12.5 实一元多项式实根隔离算法 246
12.5.1 Sturm序列 246
12.5.2 由Sturm序列给出的实根隔离算法 248
12.6 分圆多项式 249
12.6.1 分圆多项式的定义及生成 249
12.6.2 分圆多项式的Graeffe检测方法 251
12.6.3 Euler反函数方法 253
12.6.4 位移分圆多项式检测 254
12.7 （一元）复合函数分解 254
12.7.1 复合函数分解算法 254
12.7.2 形式幂级数的基本操作 257
第13章 代数方程组求解 260
13.1 结式 261
13.2 吴方法 262
13.2.1 基本概念 262
13.2.2 升列 263
13.2.3 基本列 265
13.2.4 特征列与解方程 265
13.3 Gr？bner基 267
13.3.1 概念与介绍 267
13.3.2 单项式理想及准备定理 269
13.3.3 Gr？bner基及其性质 271
13.3.4 Buchberger算法及约化Gr？bner基 274
13.3.5 Buchberger算法的两个改进 275
13.3.6 Gr？bner基的应用 281
13.3.7 Gr？bner基和特征值法解方程组 285
第14章 符号极限 287
14.1 古典方法 287
14.1.1 复合函数 287
14.1.2 代数变换与级数近似 288
14.1.3 夹逼引理 289
14.1.4 L'Hospital法则 289
14.2 Gruntz算法 291
14.2.1 指对数函数域 291
14.2.2 可比类 292
14.2.3 极大可比类 294
14.2.4 Gruntz算法 296
第15章 符号求和 298
15.1 多项式级数求和 298
15.2 超几何级数 301
15.2.1 Gosper算法 302
15.2.2 极大阶乘分解 302
第16章 符号积分 306
16.1 有理函数积分 307
16.1.1 部分分式分解 307
16.1.2 Hermite方法 308
16.1.3 Horowitz-Ostrogradsky方法 309
16.1.4 Rothstein-Trager方法 310
16.1.5 Lazard-Rioboo-Trager方法 312
16.2 Liouville定理 312
16.3 超越对数函数积分 314
16.3.1 分解引理 314
16.3.2 多项式部分 315
16.3.3 有理部分与对数部分 317
16.4 超越指数函数积分 319
16.4.1 分解引理 319
16.4.2 多项式部分 321
16.4.3 有理部分和对数部分 322
第17章 微分方程符号解 323
17.1 Risch微分方程 323
17.1.1 有理函数域 324
17.1.2 一般情形 326
17.2 一阶线性微分方程 327
17.3 微分Galois理论 328
17.4 Lie-Kolchin定理 331
17.5 二阶线性微分方程 331
17.6 高阶线性微分方程的多项式解和有理解 341
17.6.1 多项式解 341
17.6.2 有理解 343
17.6.3 平衡分解 345
17.7 高阶线性微分方程的指数解 346
17.7.1 Riccati指数与Riccati界 346
17.7.2 多项式部分 347
17.7.3 有理部分 348
17.8 二阶微分方程的特殊函数解 348
17.8.1 变量替换 349
17.8.2 有理函数Z的求解 350
17.8.3 经典特殊函数 351
附录A maTHμ系统简介 353
A.1 系统架构与特点 353
A.2 基本功能 355
A.3 网络计算平台 358
索引 360
参考文献 366