目录

第1章整除1

1.1整除的概念1

1.2欧几里得算法3

1.3扩展的欧几里得算法8

1.4算术基本定理12

思考题14第2章同余15

2.1同余和剩余类15

2.2简化剩余系、欧拉定理与费马小定理17

2.3模运算和同余的应用21

2.3.1密码系统的基本概念模型21

2.3.2移位密码算法22

2.3.3维吉尼亚密码算法22

2.3.4希尔密码算法23

思考题23第3章同余式25

3.1一次同余式25

3.1.1一次同余式的求解方法25

3.1.2一次同余式在仿射加密中的应用28

3.2中国剩余定理及其算法29

3.3同余式的应用32

3.3.1RSA公钥密码系统32

3.3.2中国剩余定理在RSA中的应用34

3.3.3模重复平方算法35

思考题37第4章二次同余式39

4.1二次同余式和平方剩余394.2勒让德符号及其计算方法42

4.3Rabin公钥密码系统49

思考题52第5章原根与阶53

5.1原根与阶的概念53

5.2原根与阶的计算方法57

5.3DiffieHellman密钥协商协议62

5.4ElGamal公钥密码系统64

思考题66第6章群67

6.1群的相关概念67

6.2子群、陪集和拉格朗日定理70

6.3正规子群、商群和同态75

6.4循环群77

6.5置换群81

6.5.1置换群的概念81

6.5.2置换群的应用84

思考题86第7章环与域87

7.1环87

7.1.1环的概念87

7.1.2环同态、环同构92

7.1.3子环、理想93

7.1.4多项式环及其求逆元算法97

7.2域104

7.2.1子域、扩域、素域和商域104

7.2.2域上多项式107

7.2.3有限域及其高斯算法求生成元108

7.3环和域在AES加密中的应用116

7.3.1AES的设计思想116

7.3.2AES中S盒的设计117

7.3.3AES中列混合的设计120

7.4环在NTRU密码体制中的应用122

思考题124第8章素性检测126

8.1素数的一些性质126

8.2费马测试算法127

8.3SolovayStrassen测试算法127

8.4MillerRabin测试算法130

思考题132第9章椭圆曲线群133

9.1椭圆曲线群的概念133

9.2椭圆曲线群的构造方法134

9.3椭圆曲线密码139

9.3.1椭圆曲线上的DiffieHellman密钥协商协议139

9.3.2ElGamal加密的椭圆曲线版本139

9.3.3椭圆曲线快速标量点乘算法140

思考题141第10章格及其算法142

10.1格、格基和正交化算法142

10.2格困难问题、高斯约减算法和LLL算法146

思考题151第11章大整数分解算法153

11.1Pollard Rho方法153

11.2Pollard p-1分解算法154

11.3随机平方法155

思考题156第12章离散对数算法157

12.1小步大步算法157

12.2Pollard Rho算法158

12.3指数演算法160

12.4PohligHellman算法161

思考题163第13章其他高级应用164

13.1平方剩余在GM加密中的应用164

13.2中国剩余定理在秘密共享中的应用166

13.2.1秘密共享的概念166

13.2.2基于中国剩余定理的简单门限方案167

13.2.3AsmuthBloom秘密共享方案168

思考题170参考文献171