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