量子計算數(shù)論

目錄
《信息科學技術學術著作叢書》序
譯者前言
原書前言
縮略語
第1章 緒論 1
1.1 數(shù)論的概念 1
1.1 節(jié)習題 8
1.2 計算數(shù)論的概念 10
1.2 節(jié)習題 22
1.3 量子計算數(shù)論的概念 24
1.3 節(jié)習題 27
1.4 本章要點及進階閱讀 27
參考文獻 28
第2章 經典計算和量子計算 32
2.1 經典計算理論 32
2.1.1 圖靈機 32
2.1.2 丘奇-圖靈論點 35
2.1.3 可判定性和可計算性 35
2.1 節(jié)習題 36
2.2 經典復雜度理論 37
2.2.1 復雜度分類 37
2.2.2 Cook-Karp論點 40
2.2 節(jié)習題 41
2.3 量子信息與量子計算 41
2.3 節(jié)習題 45
2.4 量子可計算性和量子復雜性 47
2.4 節(jié)習題 49
2.5 本章要點及進階閱讀 51
參考文獻 52
第3章 分解整數(shù)的量子算法 55
3.1 分解整數(shù)的經典算法 55
3.1.1 基本概念 55
3.1.2 數(shù)域篩法 57
3.1.3 ρ分解方法 67
3.1 節(jié)習題 70
3.2 基于整數(shù)分解問題的密碼體制 73
3.2 節(jié)習題 84
3.3 分解整數(shù)的Shor算法 87
3.3.1 量子尋階算法 87
3.3.2 量子整數(shù)分解算法 93
3.3.3 破解RSA密碼體制的量子算法 95
3.3 節(jié)習題 98
3.4 量子整數(shù)分解算法的其他變體 99
3.4 節(jié)習題 106
3.5 本章要點及進階閱讀 106
參考文獻 107
第4章 針對離散對數(shù)問題的量子計算 114
4.1 針對離散對數(shù)問題的經典算法 114
4.1.1 基本概念 114
4.1.2 Shanks的大步小步算法 115
4.1.3 Silver-Pohlig-Hellman算法 118
4.1.4 針對離散對數(shù)問題的ρ方法 123
4.1.5 Index Calculus算法 125
4.1.6 利用函數(shù)域篩法求解小特征域上的離散對數(shù) 131
4.1 節(jié)習題 135
4.2 基于離散對數(shù)問題的密碼體制 136
4.2.1 Diffie-Hellman-Merkle密鑰交換協(xié)議 137
4.2.2 ElGamal密碼體制 139
4.2.3 Massey-Omura密碼體制 141
4.2.4 基于離散對數(shù)問題的數(shù)字簽名 143
4.2 節(jié)習題 145
4.3 針對離散對數(shù)問題的量子算法 148
4.3.1 基本概念 148
4.3.2 易解離散對數(shù)問題的量子算法 150
4.3.3 針對一般情形離散對數(shù)問題的量子算法 152
4.3.4 量子離散對數(shù)算法的其他變形 155
4.3 節(jié)習題 161
4.4 本章要點及進階閱讀 161
參考文獻 163
第5章 針對橢圓曲線離散對數(shù)問題的量子計算 168
5.1 求解橢圓曲線離散對數(shù)問題的經典算法 168
5.1.1 基本概念 168
5.1.2 針對橢圓曲線離散對數(shù)問題的Pohlig-Hellman算法 168
5.1.3 針對橢圓曲線離散對數(shù)問題的大步小步算法 170
5.1.4 針對橢圓曲線離散對數(shù)問題的ρ方法 171
5.1.5 針對橢圓曲線離散對數(shù)問題的Xedni方法 175
5.1.6 橢圓曲線離散對數(shù)問題最新進展 179
5.1 節(jié)習題 182
5.2 基于橢圓曲線離散對數(shù)問題的密碼學 185
5.2.1 基本概念 185
5.2.2 橢圓曲線密碼學中的預處理 186
5.2.3 基于橢圓曲線的Diffie-Hellman-Merkle協(xié)議 187
5.2.4 基于橢圓曲線的Massey-Omura協(xié)議 189
5.2.5 基于橢圓曲線的ElGamal密碼 192
5.2.6 Menezes-Vanstone密碼體制 194
5.2.7 基于橢圓曲線的數(shù)字簽名算法 196
5.2 節(jié)習題 197
5.3 針對橢圓曲線離散對數(shù)問題的量子算法 204
5.3.1 基本概念 204
5.3.2 針對橢圓曲線離散對數(shù)問題的Eicher-Opoku量子算法 208
5.3.3 針對橢圓曲線離散對數(shù)問題的Proos-Zalka量子攻擊算法 211
5.3.4 針對ECDLP/ECC量子算法的改進算法 213
5.3 節(jié)習題 214
5.4 本章要點及進階閱讀 215
參考文獻 216
第6章 針對其他數(shù)論難題的量子算法 220
6.1 求解Pell方程 220
6.1 節(jié)習題 226
6.2 數(shù)論猜想驗證 227
6.2.1 黎曼猜想驗證 227
6.2.2 BSD猜想驗證 228
6.2 節(jié)習題 230
6.3 其他量子算法 230
6.4 本章要點及進階閱讀 232
參考文獻 233