信息安全数学基础 第2版PDF电子书下载

第1章 整数的可除性 1

1.1 整除的概念、欧几里得除法 1

1.1.1 整除的概念 1

1.1.2 Eratoshenes筛法 4

1.1.3 欧几里得除法——最小非负余数 6

1.1.4 素数的平凡判别 7

1.1.5 欧几里得除法——一般余数 7

1.2 整数的表示 9

1.2.1 b进制 9

1.2.2 计算复杂性 15

1.3 最大公因数与广义欧几里得除法 20

1.3.1 最大公因数 20

1.3.2 广义欧几里得除法及计算最大公因数 22

1.3.3 Bézout等式 24

1.3.4 Bézout等式的证明 27

1.3.5 最大公因数的进一步性质 33

1.3.6 多个整数的最大公因数及计算 36

1.3.7 形为2a-1的整数及其最大公因数 37

1.4 整除的进一步性质及最小公倍数 37

1.4.1 整除的进一步性质 37

1.4.2 最小公倍数 38

1.4.3 最小公倍数与最大公因数 39

1.4.4 多个整数的最小公倍数 40

1.5 整数分解 41

1.6 素数的算术基本定理 42

1.6.1 算术基本定理 42

1.6.2 算术基本定理的应用 44

1.7 素数定理 47

1.8 习题 48

第2章 同余 53

2.1 同余的概念及基本性质 53

2.1.1 同余的概念 53

2.1.2 同余的判断 54

2.1.3 同余的性质 59

2.2 剩余类及完全剩余系 62

2.2.1 剩余类与剩余 62

2.2.2 完全剩余系 64

2.2.3 两个模的完全剩余系 65

2.2.4 多个模的完全剩余系 66

2.3 简化剩余系与欧拉函数 67

2.3.1 欧拉函数 67

2.3.2 简化剩余类与简化剩余系 68

2.3.3 两个模的简化剩余系 72

2.3.4 欧拉函数的性质 73

2.4 欧拉定理、费马小定理和Wilson定理 76

2.4.1 欧拉定理 76

2.4.2 费马小定理 78

2.4.3 Wilson定理 79

2.5 模重复平方计算法 80

2.6 习题 88

第3章 同余式 91

3.1 基本概念及一次同余式 91

3.1.1 同余式的基本概念 91

3.1.2 一次同余式 92

3.2 中国剩余定理 95

3.2.1 中国剩余定理：“物不知数”与韩信点兵 95

3.2.2 两个方程的中国剩余定理 98

3.2.3 中国剩余定理之构造证明 99

3.2.4 中国剩余定理之递归证明 101

3.2.5 中国剩余定理之应用——算法优化 104

3.3 高次同余式的解数及解法 109

3.3.1 高次同余式的解数 109

3.3.2 高次同余式的提升 111

3.3.3 高次同余式的提升——具体应用 113

3.4 素数模的同余式 115

3.4.1 素数模的多项式欧几里得除法 115

3.4.2 素数模的同余式的简化 116

3.4.3 素数模的同余式的因式分解 117

3.4.4 素数模的同余式的解数估计 118

3.5 习题 121

第4章 二次同余式与平方剩余 125

4.1 一般二次同余式 125

4.2 模为奇素数的平方剩余与平方非剩余 128

4.3 勒让得符号 131

4.3.1 勒让得符号之运算性质 131

4.3.2 高斯引理 134

4.4 二次互反律 137

4.5 雅可比符号 143

4.6 模平方根 146

4.6.1 模p平方根 146

4.6.2 模p平方根 149

4.6.3 模m平方根 155

4.7 x2+y2=p 159

4.8 习题 163

第5章 原根与指标 166

5.1 指数及其基本性质 166

5.1.1 指数 166

5.1.2 指数的基本性质 168

5.1.3 大指数的构造 173

5.2 原根 178

5.2.1 模p原根 178

5.2.2 模pα原根 181

5.2.3 模2α指数 184

5.2.4 模m原根 186

5.3 指标及n次同余式 191

5.3.1 指标 191

5.3.2 n次同余式 193

5.4 习题 196

第6章 素性检验 198

6.1 伪素数 198

6.1.1 伪素数Fermat素性检验 198

6.1.2 无穷多伪素数 201

6.1.3 平方因子的判别 202

6.1.4 Carmicheal数 203

6.2 Euler伪素数 204

6.2.1 Euler伪素数、Solovay-Stassen素性检验 204

6.2.2 无穷多Euler伪素数 208

6.3 强伪素数 209

6.3.1 强伪素数、Miller-Rabin素性检验 209

6.3.2 无穷多强伪素数 210

6.4 习题 211

第7章 连分数 212

7.1 简单连分数 212

7.1.1 简单连分数构造 212

7.1.2 简单连分数的渐近分数 214

7.1.3 重要常数e，π，γ的简单连分数 216

7.2 连分数 218

7.2.1 基本概念及性质 218

7.2.2 连分数的渐近分数 221

7.3 简单连分数的进一步性质 224

7.4 最佳逼近 225

7.5 循环连分数 227

7.6 ？与因数分解 227

7.7 习题 230

第8章 群 232

8.1 群 232

8.1.1 基本定义 232

8.1.2 子群 241

8.2 正规子群和商群 243

8.2.1 陪集的拉格朗日定理 243

8.2.2 陪集的进一步性质 245

8.2.3 正规子群和商群 247

8.3 同态和同构 248

8.3.1 基本概念 248

8.3.2 同态分解定理 250

8.3.3 同态分解定理的进一步性质 251

8.4 习题 253

第9章 群的结构 255

9.1 循环群 255

9.1.1 循环群 255

9.1.2 循环子群的构造 255

9.2 有限生成交换群 259

9.3 置换群 261

9.4 习题 266

第10章 环与理想 267

10.1 环 267

10.1.1 基本定义 267

10.1.2 零因子环 269

10.1.3 整环及域 270

10.1.4 交换环上的整除 271

10.2 同态 272

10.3 特征及素域 272

10.4 分式域 273

10.5 理想和商环 276

10.5.1 理想 276

10.5.2 商环 281

10.5.3 环同态分解定理 282

10.6 素理想 283

10.7 习题 285

第11章 多项式环 287

11.1 多项式整环 287

11.2 多项式整除与不可约多项式 288

11.3 多项式欧几里得除法 290

11.4 多项式同余 296

11.5 本原多项式 300

11.6 多项式理想 303

11.7 多项式结式与判别式 303

11.8 习题 307

第12章 域和Galois理论 309

12.1 域的扩张 309

12.1.1 域的有限扩张 309

12.1.2 域的代数扩张 312

12.2 Galois基本定理 315

12.2.1 K-同构 315

12.2.2 Galois基本定理概述 319

12.2.3 基本定理之证明 323

12.3 可分域、代数闭包 324

12.3.1 可分域 324

12.3.2 代数闭包 324

12.4 习题 325

第13章 域的结构 327

13.1 超越基 327

13.2 有限域的构造 327

13.3 有限域的Galois群 329

13.3.1 有限域的Frobenius映射 329

13.3.2 有限域的Galois群概述 334

13.4 正规基 335

13.5 习题 338

第14章 椭圆曲线 340

14.1 椭圆曲线基本概念 340

14.2 加法原理 342

14.2.1 实数域R上椭圆曲线 345

14.2.2 素域Fp（p＞3）上的椭圆曲线E 347

14.2.3 域F2n（n≥1）上的椭圆曲线E,j（E）≠0 355

14.3 有限域上的椭圆曲线的阶 358

14.4 重复倍加算法 359

14.5 习题 361

第15章 AKS素性检验 362

附录A 三个数学难题 364

附录B 周期序列 365

附录C 前1280个素数及其原根表 367

附录D F359 375

D.1 域F359中生成元g=7的幂指表：由k得到h=gk 375

D.2 域F359中生成元g=7的指数表：由h得到gk=h 378

附录E F28=F2[x](x8+x4+x3+x2+1) 380

E.1 域中生成元g=x的幂指表：由k得到h=gk 380

E.2 域中生成元g=x的指数表：由h得到gk=h 384

E.3 域中生成元g=x的幂的函数u2+u表：由k得到h=g2k+gk 388

E.4 域中生成元g=x的广义指数表：由h得到g2k+gk=h 392

附录F F28=F2[x](x8+x4+x3+x+1) 396

F.1 域中生成元g=x+1的幂指表：由k得到h=gk 396

F.2 域中生成元g=x+1的指数表：由h得到gk=h 400

F.3 域中生成元g=x+1的幂的函数u2+u表：由k得到h=g2k+gk 404

F.4 域中生成元g=x+1的广义指数表：由h得到g2k+gk=h 408

索引 412

参考文献 416