目录

第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.3Toom-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.1Solovay-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 p . 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.2m进方法,窗口方法及加法链.............................................. 47

4.1.3Montgomery约化........................................................ 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.5dmod与bmod........................................................... 57

4.3.6Jebelean-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,a)............................................................ 68

4.7.3计算φ(x,a)............................................................. 69

4.7.4 计算S .................................................................. 70

4.7.5计算S1................................................................. 70

4.7.6计算S3................................................................. 71

4.7.7计算S2................................................................. 71

目录ix

·· 

4.7.8 计算V .................................................................. 71

4.7.9计算V2................................................................. 72

4.8第n个素数pn................................................................ 73

4.9M¨obius函数μ(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.2Pad′e逼近与有理函数重建................................................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.4Z[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.1Frobenius映射和Berlekamp子代数...................................... 175

9.5.2Berlekamp算法的实现...................................................176

9.6 各算法复杂度比较........................................................... 178

9.7 不可约性检测和不可约多项式的构造......................................... 178第10章整系数多项式因子分解..................................................... 182

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

10.2 Hensel 提升理论............................................................ 187

10.2.1 Hensel 单步算法....................................................... 187

目录xi

·· 

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.2Fp[x1,x2,,xn]上最大公因子......................................... 214

··· 

11.2.3多元多项式的“Mignotte”界............................................. 215

11.2.4Z[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分圆多项式的Grae.e检测方法.......................................... 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¨obner 基................................................................. 267

13.3.1 概念与介绍............................................................ 267

13.3.2 单项式理想及准备定理..................................................269

13.3.3Gr¨obner基及其性质....................................................271

13.3.4Buchberger算法及约化Gr¨obner基...................................... 274

13.3.5Buchberger算法的两个改进.............................................275

13.3.6Gr¨obner基的应用......................................................281

目录xiii

·· 

13.3.7Gr¨obner基和特征值法解方程组......................................... 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.4Gruntz算法........................................................... 296第15章符号求和................................................................... 298

15.1 多项式级数求和.............................................................298

15.2 超几何级数................................................................. 301

15.2.1Gosper算法........................................................... 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.1Riccati指数与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附录AmaTHμ系统简介........................................................... 353

A.1 系统架构与特点............................................................. 353

A.2 基本功能.................................................................... 355

A.3 网络计算平台............................................................... 358 索引...................................................................................360 参考文献.............................................................................. 366