数论算法PDF|Epub|txt|kindle电子书版本网盘下载

数论算法PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 整数的可除性1

1.1 整除的概念与带余除法1

1.1.1 整除及其性质1

1.1.2 素数4

1.1.3 带余除法5

1.2 整数的表示7

1.3 最大公因数与辗转相除法8

1.3.1 最大公因数8

1.3.2 辗转相除法13

1.3.3 求（a，b）的算法14

1.3.4 （a，b）与a、b的关系17

1.3.5 其他性质22

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

1.4.1 整除和最大公因数的其他性质25

1.4.2 最小公倍数及其性质26

1.5 算术基本定理28

习题132

第2章 数论函数38

2.1 数论函数38

2.2 函数「x」、「x」、［x]38

2.2.1 下整数函数「x」38

2.2.2 上整数函数「x］39

2.2.3 四舍五入函数［x］39

2.3 函数potpn40

2.4 Euler函数？（n）43

2.5 墨比乌斯函数μ（n）50

2.5.1 墨比乌斯函数50

2.5.2 墨比乌斯反演公式53

2.6 素数个数函数π（n）56

2.7 数论函数的狄利克雷乘积57

2.8 积性函数60

2.8.1 积性函数的定义61

2.8.2 积性函数的性质62

习题265

第3章 同余及其运算71

3.1 同余的概念及基本性质71

3.2 剩余类及完全剩余系77

3.2.1 剩余类和完全剩余系77

3.2.2 剩余类的性质79

3.3 既约剩余系80

3.3.1 既约剩余系80

3.3.2 整数a模m的逆84

3.4 欧拉定理和费马小定理87

3.4.1 欧拉定理87

3.4.2 费马小定理89

3.5 模重复平方计算法91

3.5.1 算法原理91

3.5.2 模重复平方计算法92

3.6 一次不定方程95

3.6.1 二元一次（不定）方程95

3.6.2 求特解的方法99

3.6.3 s元一次不定方程103

3.6.4 （s元）一次不定方程组104

3.7 矩阵的同余运算107

3.7.1 矩阵及其线性运算107

3.7.2 矩阵乘法109

3.7.3 可逆矩阵111

3.8 同余的应用113

3.8.1 RSA公钥密码算法113

3.8.2 背包公钥密码算法114

3.8.3 希尔密码算法116

3.8.4 随机数的Lehmer生成算法118

3.8.5 随机数的BBS生成算法120

习题3121

第4章 同余方程126

4.1 基本概念126

4.2 一次同余方程134

4.3 中国剩余定理140

4.4 高次同余方程的解数及解法152

4.4.1 解数152

4.4.2 特殊情形的解法154

4.4.3 一般情形的解法161

4.5 素数模的同余方程165

4.5.1 同余方程的化简165

4.5.2 解数的判断168

4.6 同余方程的应用170

4.6.1 密钥分存170

4.6.2 数据库加密方案173

4.6.3 BBS流密码算法174

习题4177

第5章 二次同余方程与平方剩余182

5.1 一般二次同余方程182

5.1.1 二次同余方程的化简182

5.1.2 平方剩余183

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

5.2.1 平方剩余的判断条件185

5.2.2 平方剩余的个数187

5.3 勒让德符号188

5.4 雅可比符号198

5.5 模p平方根205

5.6 模数为合数的情形209

5.6.1 p为奇素数210

5.6.2 p=2210

5.7 解同余方程小结215

习题5215

第6章 原根与离散对数221

6.1 整数的阶及其性质221

6.1.1 整数的阶和原根221

6.1.2 阶的性质与计算方法222

6.2 原根的存在性与计算方法235

6.3 离散对数244

6.4 离散对数的计算247

6.4.1 Pohlid-Hellman算法247

6.4.2 Shank算法252

6.5 二项同余方程与n次剩余254

6.6 原根与离散对数的应用257

6.6.1 Diffie-Hellman密钥交换算法257

6.6.2 ElGamal加密算法258

6.6.3 改进的随机数生成算法261

6.6.4 一种快速傅里叶变换算法263

6.6.5 同余方程的求解264

6.7 单向函数266

习题6267

第7章 连分数271

7.1 连分数271

7.1.1 连分数的概念271

7.1.2 连分数性质与渐进连分数的计算274

7.2 简单连分数279

7.2.1 实数的简单连分数的生成279

7.2.2 有理分数的连分数表示281

7.3 循环连分数283

习题7284

第8章 素性测试和整数分解287

8.1 素性测试的精确方法287

8.2 伪素数与Fcrmat测试算法289

8.3 Euler伪素数与Solovay-Stassen测试算法292

8.3.1 Euler伪素数292

8.3.2 Solovay-Stassen测试算法293

8.4 强伪素数与Miller-Rabin测试算法293

8.4.1 强伪素数295

8.4.2 Miller-Rabin测试算法295

8.5 正整数的分解297

8.5.1 Fermat方法298

8.5.2 Fermat方法的拓展299

8.5.3 Legcndre方法299

8.5.4 Pollard方法300

8.5.5 Kraitchik方法301

8.5.6 B基数法——Brillhart-Morrison法303

8.5.7 连分数法306

8.5.8 二次筛法308

8.5.9 p—1法310

习题8312

第9章 有限域314

9.1 集合及其运算314

9.1.1 集合314

9.1.2 映射315

9.1.3 代数运算317

9.1.4 同构映射317

9.2 群319

9.3 环323

9.3.1 环323

9.3.2 多项式环325

9.4 域329

9.4.1 域的概念329

9.4.2 域的特征和同构332

9.4.3 有限域及其结构335

9.4.4 有限域的构造337

9.4.5 GF（2n）域上的计算341

习题9343

附录A 素数表与最小正原根表（1200以内）345

附录B ？的连分数346

附录C F2上的既约多项式（n≤10）348

附录D F2上的本原多项式350

索引352

参考文献361