算法數論九講
許光午
相關主題
商品描述
本書是新一代信息技術網絡空間安全高等教育系列教材之一，以九講來介紹算法數論的主要內容。前四講的內容是數論的基本概念和基礎算法，特別地，具有現代計算意義的中國古代數論算法及其拓展在前三講中得到了充分的解釋，第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
