计算机代数系统的数学原理PDF电子书下载

第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