第1章整除1

1.1整除的概念、素数与合数1

1.2最大公因子、最小公倍数和算术基本定理4

1.2.1带余数除法4

1.2.2最大公因子6

1.2.3最小公倍数7

1.2.4算术基本定理9

1.3Euclid算法10

1.3.1Euclid定理10

1.3.2广义Euclid除法11

习题13

第2章数论函数15

2.1数论函数的定义15

2.2函数τ(n)和σ(n)17

2.3函数μ(n)及Mbius变换18

2.4函数φ(n)20

习题22

第3章同余23

3.1同余的概念及性质23

3.2剩余类与剩余系25

3.3简化剩余类与简化剩余系26

3.4Euler函数27

3.5Euler定理、Fermat定理及Wilson定理28

3.6求余运算与模运算29

3.7模指数运算31

习题32网络空间安全数学基础目录第4章同余方程34

4.1同余方程的基本概念34

4.2一次同余方程35

4.3一次同余方程组和中国剩余定理36

4.4模为素数的高次同余方程41

4.5模数为素数幂的同余方程44

习题46

第5章二次同余方程47

5.1二次同余方程的概念及二次剩余47

5.2Legendre符号50

5.3Jacobi符号55

5.4Rabin密码体制58

习题60

第6章原根和指标62

6.1指数和原根62

6.2指标与二项同余方程69

习题72

第7章代数系统和群73

7.1代数系统73

7.2群74

7.3子群和群同态77

7.4正规子群和商群79

习题84

第8章环和域85

8.1环和域的基本概念85

8.2子环和理想89

8.3多项式环90

习题93

第9章有限域94

9.1有限域的性质94

9.1.1有限域上的运算94

9.1.2有限域的加法结构95

9.1.3有限域的乘法结构95

9.2有限域的构造97

9.2.1最小多项式97

9.2.2有限域的存在性和唯一性99

9.3有限域上多项式的分解103

9.4有限域上的椭圆曲线点群110

9.4.1椭圆曲线110

9.4.2有限域上的椭圆曲线111

9.4.3椭圆曲线上的点数113

9.5椭圆曲线上的倍点运算113

习题115

第10章素性检验117

10.1Lucas确定性算法117

10.2Fermat可能素数和Euler可能素数118

10.3强可能素数120

10.4Lucas可能素数122

10.5Mersenne素数123

10.6椭圆曲线素性检验124

习题125

第11章整数分解126

11.1Fermat法126

11.2连分数法128

11.2.1连分数的概念128

11.2.2连分数的性质130

11.2.3连分数分解法132

11.3筛法134

11.3.1二次筛法134

11.3.2多重多项式的二次筛法134

11.4Pollard法135

11.4.1Pollard Rho法135

11.4.2P-1法136

11.4.3P+1法136

11.4.4椭圆曲线法137

习题138第12章离散对数139

12.1大步小步法139

12.1.1Shanks的大步小步法139

12.1.2Pollard Rho算法140

12.2SilverPohligHellman算法141

12.2.1p=2n+1时的SilverPohligHellman算法141

12.2.2任意素数时的SilverPohligHellman算法141

12.3指标法142

12.3.1Adleman的指标计算法142

12.3.2椭圆曲线上的指标计算143

习题143

参考文献144

第1章整除1

1.1整除的概念、素数与合数1

1.2最大公因子、最小公倍数、算术基本定理3

1.2.1带余数除法3

1.2.2最大公因子5

1.2.3最小公倍数10

1.2.4算术基本定理13

1.3Euclid算法17

1.3.1Euclid定理18

1.3.2广义Euclid除法19

习题20

第2章数论函数21

2.1数论函数的定义24

2.2函数τ(n)和σ(n)25

2.3函数μ(n)及Mbius变换27

2.4函数φ(n)28

习题30

第3章同余31

3.1同余的概念及性质33

3.2剩余类与剩余系35

3.3简化剩余类与简化剩余系36

3.4Euler函数38

3.5Euler定理、Fermat定理及Wilson定理39

3.6求余运算与模运算43

3.7模指数运算44

第4章同余方程45网络空间安全数学基础目录4.1同余方程的基本概念46

4.2一次同余方程47

4.3一次同余方程组和中国剩余定理49

4.4模为素数的高次同余方程53

4.5模数为素数幂的同余方程55

习题62

第5章二次同余方程63

5.1二次同余方程的概念及二次剩余63

5.2Legendre符号65

5.3Jacobi符号75

5.4Rabin密码体制80

习题82

第6章原根和指标83

6.1指数和原根83

6.2指标与二项同余方程88

习题97

第7章代数系统和群98

7.1代数系统98

7.2群100

7.3子群和群同态105

7.4正规子群和商群110

习题114

第8章环和域115

8.1环和域的基本概念115

8.2子环和理想118

8.3多项式环124

习题127

第9章有限域128

9.1有限域的性质128

9.1.1有限域上的运算128

9.1.2有限域的加法结构130

9.1.3有限域的乘法结构134

9.2有限域的构造138

9.2.1最小多项式138

9.2.2有限域的存在性和唯一性140

9.3有限域上多项式的分解142

9.4有限域上的椭圆曲线点群145

9.4.1椭圆曲线145

9.4.2有限域上的椭圆曲线148

9.4.3椭圆曲线上的点数153

9.5椭圆曲线上的倍点运算156

习题158

第10章素性检验159

10.1Lucas确定性算法163

10.2Fermat可能素数和Euler可能素数165

10.3强可能素数166

10.4Lucas可能素数168

10.5Mersenne素数169

10.6椭圆曲线素性检验170

习题171

第11章整数分解172

11.1Fermat法172

11.2连分数法173

11.2.1连分数的概念175

11.2.2连分数的性质177

11.2.3连分数分解法178

11.3筛法180

11.3.1二次筛法180

11.3.2多重多项式的二次筛法181

11.4Pollard法183

11.4.1Pollard Rho法183

11.4.2P-1法185

11.4.3P+1法186

11.4.4椭圆曲线法187

习题188

第12章离散对数189

12.1大步小步法189

12.1.1Shanks的大步小步法190

12.1.2Pollard Rho算法190

12.2SilverPohligHellman算法191

12.2.1p=2n+1时192

12.2.2任意素数时193

12.3指标法193

12.3.1Adleman的指标计算法194

12.3.2椭圆曲线上的指标计算194

习题195

参考文献196