目錄
叢書序
序言
前言
第1講 基本概念和歷史注記 1
1.1 基本概念 1
1.2 古代算術(shù)方法 11
1.3 無窮之階與計算復(fù)雜度 13
1.4 練習(xí)題 15
第2講 大衍求一術(shù)的探源和擴展 17
2.1 大衍求一術(shù)和它的基本性質(zhì) 18
2.2 狀態(tài)矩陣與連分數(shù) 24
2.3 狀態(tài)矩陣與二維格 30
2.4 練習(xí)題 36
第3講 中國剩余定理及其計算意義 38
3.1 中國剩余定理.38
3.2 有限傅里葉變換 45
3.3 密碼學(xué)應(yīng)用和其他計算應(yīng)用 48
3.3.1 RSA 解密運算 48
3.3.2 Pohlig-Hellman算法 49
3.3.3 中國剩余定理與并行計算 51
3.4 練習(xí)題 55
第4講 大整數(shù)乘法 57
4.1 快速傅里葉變換 57
4.2 大整數(shù)乘法的算法演進 60
4.2.1 Karatsuba算法 60
4.2.2 Sch.nhage-Strassen大整數(shù)乘法算法 62
4.3 大整數(shù)乘法的最新突破 67
4.3.1 Sch.nhage-Strassen第一個乘法算法 67
4.3.2 多維離散傅里葉變換和幾個特別的技術(shù) 68
4.3.3 高斯重采樣技術(shù) 71
4.3.4 復(fù)雜度 72
4.4 練習(xí)題 72
第5講 模乘算法 74
5.1 Montgomery算法 74
5.2 Barrett歸約算法 77
5.3 特殊形式素模數(shù)的計算.79
5.3.1 模p=bt-a歸約方法 80
5.3.2 SM2的模乘優(yōu)化方法 80
5.4 練習(xí)題 82
第6講 素數(shù)與相關(guān)算法 83
6.1 關(guān)于素數(shù)分布的一些結(jié)論 83
6.1.1 素數(shù)定理 83
6.1.2 切比雪夫定理與素數(shù)密度 84
6.2 素檢測算法 89
6.2.1 概率算法 89
6.2.2 確定性算法 95
6.3 廣義黎曼假設(shè)下的幾個數(shù)論算法 97
6.3.1 廣義黎曼假設(shè) 97
6.3.2 Tonelli–Shanks算法 99
6.3.3 原根的計算 101
6.4 練習(xí)題 102
第7講 整數(shù)分解方法 104
7.1 連分數(shù)分解方法 104
7.1.1 二次無理數(shù)的連分數(shù)及其周期性 104
7.1.2 整數(shù)分解的連分數(shù)方法 109
7.2 二次篩法 112
7.3 數(shù)域篩法 116
7.4 練習(xí)題 119
第8講 離散對數(shù)解法 120
8.1 離散對數(shù)的一般解法120
8.1.1 Shanks的大步小步算法 120
8.1.2 Pollard算法 123
8.2 指標(biāo)計算方法 127
第9講 整數(shù)的特殊表示及應(yīng)用 130
9.1 代數(shù)數(shù)基進制下的稀疏表示 130
9.1.1 Z[τ]的歐氏性質(zhì)和τ冪的整除判別法 131
9.1.2 Z[τ]中元素的稀疏τ進制展開 135
9.2 雙基方法 139
9.3 練習(xí)題 142
參考文獻 143
附錄：群、環(huán)和域 146
索引 150