算法数论九讲

本书是新一代信息技术网络空间安全高等教育系列教材之一，以九讲来介绍算法数论的主要内容。前四讲的内容是数论的基本概念和基础算法，特别地，具有现代计算意义的中国古代数论算法及其拓展在前三讲中得到了充分的解释，第4讲介绍计算中根本算法——大整数乘法的技术与方法。第5讲是关于模乘的现代算法，体现了计算工具对数论算法发展的影响。第6讲介绍素数与相关算法的课题。尽管密码学的应用已经穿插在每讲之中，强调起见，还专门为公钥密码学的数学困难问题和计算问题设立了三讲，包括整数分解，离散对数和有重要密码学应用的整数的两个特殊表示，以期加深读者对算法数论的理解与掌握。

目录
丛书序
序言
前言
第1讲 基本概念和历史注记 1
1.1 基本概念 1
1.2 古代算术方法 11
1.3 无穷之阶与计算复杂度 13
1.4 练习题 15
第2讲 大衍求一术的探源和扩展 17
2.1 大衍求一术和它的基本性质 18
2.2 状态矩阵与连分数 24
2.3 状态矩阵与二维格 30
2.4 练习题 36
第3讲 中国剩余定理及其计算意义 38
3.1 中国剩余定理.38
3.2 有限傅里叶变换 45
3.3 密码学应用和其他计算应用 48
3.3.1 RSA 解密运算 48
3.3.2 Pohlig-Hellman算法 49
3.3.3 中国剩余定理与并行计算 51
3.4 练习题 55
第4讲 大整数乘法 57
4.1 快速傅里叶变换 57
4.2 大整数乘法的算法演进 60
4.2.1 Karatsuba算法 60
4.2.2 Sch.nhage-Strassen大整数乘法算法 62
4.3 大整数乘法的最新突破 67
4.3.1 Sch.nhage-Strassen第一个乘法算法 67
4.3.2 多维离散傅里叶变换和几个特别的技术 68
4.3.3 高斯重采样技术 71
4.3.4 复杂度 72
4.4 练习题 72
第5讲 模乘算法 74
5.1 Montgomery算法 74
5.2 Barrett归约算法 77
5.3 特殊形式素模数的计算.79
5.3.1 模p=bt-a归约方法 80
5.3.2 SM2的模乘优化方法 80
5.4 练习题 82
第6讲 素数与相关算法 83
6.1 关于素数分布的一些结论 83
6.1.1 素数定理 83
6.1.2 切比雪夫定理与素数密度 84
6.2 素检测算法 89
6.2.1 概率算法 89
6.2.2 确定性算法 95
6.3 广义黎曼假设下的几个数论算法 97
6.3.1 广义黎曼假设 97
6.3.2 Tonelli–Shanks算法 99
6.3.3 原根的计算 101
6.4 练习题 102
第7讲 整数分解方法 104
7.1 连分数分解方法 104
7.1.1 二次无理数的连分数及其周期性 104
7.1.2 整数分解的连分数方法 109
7.2 二次筛法 112
7.3 数域筛法 116
7.4 练习题 119
第8讲 离散对数解法 120
8.1 离散对数的一般解法120
8.1.1 Shanks的大步小步算法 120
8.1.2 Pollard算法 123
8.2 指标计算方法 127
第9讲 整数的特殊表示及应用 130
9.1 代数数基进制下的稀疏表示 130
9.1.1 Z[τ]的欧氏性质和τ幂的整除判别法 131
9.1.2 Z[τ]中元素的稀疏τ进制展开 135
9.2 双基方法 139
9.3 练习题 142
参考文献 143
附录：群、环和域 146
索引 150