包邮算法数论九讲

目录 丛书序 序言 前言 第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**个乘法算法 674.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算法 1238.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