信息安全数学基础

第1章 整数的可除性

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

1.1.1 整除的概念

1.1.2 Eratoshenes筛法

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

1.1.4 素数的平凡判别

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

1.2 整数的表示

1.2.1 b进制

1.2.2 计算复杂性

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

1.3.1 最大公因数

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

1.3.3 Bezout等式

1.3.4 Bezout等式的证明

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

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

1.3.7 形为 2a1的整数及其最大公因数

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

1.4.1 整除的进一步性质

1.4.2 最小公倍数

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

1.4.4 多个整数的最小公倍数

1.5 整数分解

1.6 素数的算术基本定理

1.6.1 算术基本定理

1.6.2 算术基本定理的应用

1.7 素数定理

1.8 习题

第2章 同余

2.1 同余的概念及基本性质

2.1.1 同余的概念

2.1.2 同余的判断

2.1.3 同余的性质

2.2 剩余类及完全剩余系

2.2.1 剩余类与剩余

2.2.2 完全剩余系

2.2.3 两个模的完全剩余系

2.2.4 多个模的完全剩余系

2.3 简化剩余系与欧拉函数

2.3.1 欧拉函数

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

2.3.3 两个模的简化剩余系

2.3.4 欧拉函数的性质

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

2.4.1 欧拉定理

2.4.2 费马小定理

2.4.3 Wilson定理

2.5 模重复平方计算法

2.6 习题

第3章 同余式

3.1 基本概念及一次同余式

3.1.1 同余式的基本概念

3.1.2 一次同余式

3.2 中国剩余定理

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

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

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

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

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

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

3.3.1 高次同余式的解数

3.3.2 高次同余式的提升

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

3.4 素数模的同余式

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

3.4.2 素数模的同余式的简化

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

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

3.5 习题

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

4.1 一般二次同余式

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

4.3 勒让得符号

4.3.1 勒让得符号之运算性质

4.3.2 高斯引理

4.4 二次互反律

4.5 雅可比符号

4.6 模平方根

4.6.1 模 p平方根

4.6.2 模 p平方根

4.6.3 模 m平方根

4.7 x2

4.8 习题

第5章 原根与指标

5.1 指数及其基本性质

5.1.1 指数

5.1.2 指数的基本性质

5.1.3 大指数的构造

5.2 原根

5.2.1 模 p原根

5.2.2 模 pα原根

5.2.3 模 2α指数

5.2.4 模 m原根

5.3 指标及 n次同余式

5.3.1 指标

5.3.2 n次同余式

5.4 习题

第6章 素性检验

6.1 伪素数

6.1.1 伪素数 Fermat素性检验

6.1.2 无穷多伪素数

6.1.3 平方因子的判别

6.1.4 Carmicheal数

6.2 Euler伪素数

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

6.2.2 无穷多 Euler伪素数

6.3 强伪素数

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

6.3.2 无穷多强伪素数

6.4 习题

第7章 连分数

7.1 简单连分数

7.1.1 简单连分数构造

7.1.2 简单连分数的渐近分数

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

7.2 连分数

7.2.1 基本概念及性质

7.2.2 连分数的渐近分数

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

7.4 最佳逼近

7.5 循环连分数

7.6 √ n与因数分解

7.7 习题

第8章 群

8.1 群

8.1.1 基本定义

8.1.2 子群

8.2 正规子群和商群

8.2.1 陪集的拉格朗日定理

8.2.2 陪集的进一步性质

8.2.3 正规子群和商群

8.3 同态和同构

8.3.1 基本概念

8.3.2 同态分解定理

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

8.4 习题

第9章 群的结构

9.1 循环群

9.1.1 循环群

9.1.2 循环子群的构造

9.2 有限生成交换群

9.3 置换群

9.4 习题

第10章 环与理想

10.1 环

10.1.1 基本定义

10.1.2 零因子环

10.1.3 整环及域

10.1.4 交换环上的整除

10.2 同态

10.3 特征及素域

10.4 分式域

10.5 理想和商环

10.5.1 理想

10.5.2 商环

10.5.3 环同态分解定理

10.6 素理想

10.7 习题

第11章 多项式环

11.1 多项式整环

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

11.3 多项式欧几里得除法

11.4 多项式同余

11.5 本原多项式

11.6 多项式理想

11.7 多项式结式与判别式

11.8 习题

第12章 域和 Galois理论

12.1 域的扩张

12.1.1 域的有限扩张

12.1.2 域的代数扩张

12.2 Galois基本定理

12.2.1 K-同构

12.2.2 Galois基本定理概述

12.2.3 基本定理之证明

12.3 可分域、代数闭包

12.3.1 可分域

12.3.2 代数闭包

12.4 习题

第13章 域的结构

13.1 超越基

13.2 有限域的构造

13.3 有限域的 Galois群

13.3.1 有限域的 Frobenius映射

13.3.2 有限域的 Galois群概述

13.4 正规基

13.5 习题

第14章 椭圆曲线

14.1 椭圆曲线基本概念

14.2 加法原理

14.2.1 实数域 R上椭圆曲线

14.2.2 素域 Fp (p> 3)上的椭圆曲线 E

14.2.3 域 F2n (n≥1)上的椭圆曲线 E, j(E)≠0

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

14.4 重复倍加算法

14.5 习题

第15章 AKS素性检验

附录A 三个数学难题

附录B 周期序列

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

附录D F359

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

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

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

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

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

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

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

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

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

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

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

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

索引

参考文献

本书用统一的数学语言和符号系统地介绍了网络与信息安全所涉及的数学理论和方法，特别是与三大难解数学问题相关的数论、代数和椭圆曲线理论等，并对一些重要算法作了详尽的推理和阐述。此外，还介绍了网络与信息安全研究和应用中所产生的新的数学成果。本书可作为网络与信息安全专业、通信安全、计算机安全和保密专业等的本科生和研究生的教学用书，也可以作为网络与信息安全的专业人员和从业人员的参考用书。