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