第1章 高精度运算

1.1　整数

1.1.1 进制转换

1.1.2　四则运算

1.2　快速乘法

1.2.1　一元多项式乘法

1.2.2　Karatsuba乘法

1.2.3　Toom-Cook乘法

1.2.4　FFT乘法

第2章 素数判定

2.1　Fermat检测

2.2　Euler检测

2.3　Lehmer N-1型检测

2.4　Lucas伪素数检测与N+1型检测

2.5　概率性检测方法

2.5.1　Solovay-Strassen检测

2.5.2　Rabin-Miller检测

2.5.3　Baillie-PSW检测

第3章 整数因子分解

3.1　试除法

3.2　Euclid算法

3.3　Pollard ρ-1方法

3.4　Pollard ρ方法

3.5　平方型分解

3.6　连分式方法

3.7　椭圆曲线方法

3.8　二次筛法

3.8.1　单个多项式二次筛法

3.8.2　多个多项式二次筛法

3.9　数域筛法

第4章 基础数论算法

4.1　快速求幂

4.1.1　二进方法

4.1.2　m进方法，窗口方法及加法链

4.1.3　Montgomery约化

4.2　幂次检测

4.2.1　整数开方

4.2.2　平方检测

4.2.3　素数幂检测

4.3　最大公因子

4.3.1　Euclid算法

4.3.2　Lehmer加速算法

4.3.3　二进方法

4.3.4　扩展Euclid算法

4.3.5　dmod与bmod

4.3.6　Jebelean-Weber-Sorenson加速算法

4.4　Legendre-Jacobi-Kronecker符号

4.5 中国剩余定理

4.6　连分数展式

4.7　素数计数函数π（x）

4.7.1　部分筛函数

4.7.2 计算P2(x,α)

4.7.3 计算φ(x,α)

4.7.4 计算S

4.7.5 计算S1

4.7.6 计算S3

4.7.7 计算S2

4.7.8 计算V

4.7.9 计算V2

4.8　第n个素数pn

4.9 M？bius函数μ（n）和Euler函数？（n）

第5章 数学常数

5.1 圆周率

5.1.1　级数方法

5.1.2 迭代方法

5.2 自然对数底

5.2.1　级数方法

5.3　对数常数

5.3.1　级数方法

5.3.2 迭代方法

5.4　Euler常数

5.4.1　级数方法

第6章　线性代数

6.1　快速矩阵乘法

6.1.1　基于向量内积算法的Winograd算法

6.1.2　Strassen算法

6.2　线性方程组与消元法

6.2.1 基于中国剩余定理的消元法

6.2.2　Padé逼近与有理函数重建

6.2.3 Hensel提升算法

6.2.4　数值算法求精确解

6.3　Wiedemann算法与黑箱方法

6.3.1　概率性算法与预处理步骤概述

6.3.2　线性递推列

6.3.3　线性方程组的Wiedemann算法

第7章 一元多项式求值和插值

7.1　求值算法

7.2　插值算法

第8章 一元多项式的最大公因子

8.1　Euclid算法

8.2　域上多项式的快速Euclid算法

8.3　结式性质及其计算

8.3.1　结式

8.3.2　Euclid算法计算结式

8.4　Z［x］中的模GCD算法

8.4.1　Mignotte界

8.4.2　大素数模公因子算法

8.4.3　小素数模公因子算法

8.5　多项式组的概率算法

第9章 有限域上多项式因子分解

9.1　不同次数因子分解

9.1.1　有限域Fp和Fpd

9.1.2 不同次因子分解

9.2　同次因子分解

9.2.1　特征为奇素数的有限域

9.2.2　特征为2的有限域

9.3　一个完整的因子分解算法及其应用

9.4　无平方因子分解

9.4.1　特征为零的域上无平方分解

9.4.2 特征有限的域上无平方分解

9.5　Berlekamp算法

9.5.1　Frobenius映射和Berlekamp子代数

9.5.2　Berlekamp算法的实现

9.6　各算法复杂度比较

9.7　不可约性检测和不可约多项式的构造

第10章 整系数多项式因子分解

10.1　大素数模方法和因子组合算法

10.2　Hensel提升理论

10.2.1　Hensel单步算法

10.2.2　利用因子树进行多因子Hensel提升

10.3　应用Hensel提升的Zassenhaus算法

10.4　格中短向量理论

10.4.1　问题的引入

10.4.2　约化基算法

10.4.3　约化基算法的细节说明

10.5　应用格中短向量的分解算法

第11章 多元多项式

11.1　多元多项式插值方法

11.1.1　稠密插值

11.1.2　稀疏插值

11.2　Euclid算法和一般模算法

11.2.1　概述

11.2.2　Fp［x1,x2,…,xn］上最大公因子

11.2.3　多元多项式的“Mignotte”界

11.2.4　Z［x1,x2,…,xn］上最大公因子

11.3　Zippel稀疏插值算法

11.3.1　一个具体的例子

11.3.2　算法描述

11.4　求GCD其他方法

11.4.1 启发式算法

11.4.2 EZ-GCD

11.5　多元多项式因子分解Kronecker算法

11.6　利用Hensel提升的因子分解算法

11.6.1　概述

11.6.2　扩展Zassenhaus算法

11.6.3　因子还原

11.6.4　预先确定因子的首项系数

第12章 一元多项式求根算法

12.1　多项式零点模估计

12.2　Jenkins-Traub算法

12.2.1　算法引入

12.2.2 收敛速度和细节说明

12.3　Laguerre算法

12.4　代数模方程求解

12.4.1　Fp中的开平方算法

12.4.2　模p代数方程求解

12.5　实一元多项式实根隔离算法

12.5.1　Sturm序列

12.5.2　由Sturm序列给出的实根隔离算法

12.6　分圆多项式

12.6.1　分圆多项式的定义及生成

12.6.2 分圆多项式的Graeffe检测方法

12.6.3　Euler反函数方法

12.6.4　位移分圆多项式检测

12.7　（一元）复合函数分解

12.7.1　复合函数分解算法

12.7.2 形式幂级数的基本操作

第13章　代数方程组求解

13.1　结式

13.2　吴方法

13.2.1　基本概念

13.2.2　升列

13.2.3　基本列

13.2.4　特征列与解方程

13.3　Gr？bner基

13.3.1　概念与介绍

13.3.2 单项式理想及准备定理

13.3.3　Gr？bner基及其性质

13.3.4　Buchberger算法及约化Gr？bner基

13.3.5　Buchberger算法的两个改进

13.3.6　Gr？bner基的应用

13.3.7　Gr？bner基和特征值法解方程组

第14章 符号极限

14.1　古典方法

14.1.1　复合函数

14.1.2　代数变换与级数近似

14.1.3　夹逼引理

14.1.4　L'Hospital法则

14.2　Gruntz算法

14.2.1　指对数函数域

14.2.2　可比类

14.2.3　极大可比类

14.2.4　Gruntz算法

第15章　符号求和

15.1　多项式级数求和

15.2　超几何级数

15.2.1　Gosper算法

15.2.2　极大阶乘分解

第16章　符号积分

16.1　有理函数积分

16.1.1　部分分式分解

16.1.2　Hermite方法

16.1.3　Horowitz-Ostrogradsky方法

16.1.4 Rothstein-Trager方法

16.1.5 Lazard-Rioboo-Trager方法

16.2 Liouville定理

16.3　超越对数函数积分

16.3.1　分解引理

16.3.2　多项式部分

16.3.3　有理部分与对数部分

16.4　超越指数函数积分

16.4.1　分解引理

16.4.2　多项式部分

16.4.3　有理部分和对数部分

第17章　微分方程符号解

17.1　Risch微分方程

17.1.1　有理函数域

17.1.2　一般情形

17.2　一阶线性微分方程

17.3　微分Galois理论

17.4　Lie-Kolchin定理

17.5　二阶线性微分方程

17.6　高阶线性微分方程的多项式解和有理解

17.6.1　多项式解

17.6.2　有理解

17.6.3　平衡分解

17.7　高阶线性微分方程的指数解

17.7.1　Riccati指数与Riccati界

17.7.2　多项式部分

17.7.3　有理部分

17.8　二阶微分方程的特殊函数解

17.8.1　变量替换

17.8.2　有理函数Z的求解

17.8.3　经典特殊函数

附录A　maTHμ系统简介

A.1　系统架构与特点

A.2　基本功能

A.3　网络计算平台

索引

参考文献