量子計算數論
作 者: (英)顏松遠(Song Y.Y) 著 段乾恆 等 譯
定 價: 120
出?版?社: 科學出版社
出版日期: 2020年04月01日
頁 數: 235
裝 幀: 平裝
ISBN: 9787030648402
●《信息科學技術學術著作叢書》序
譯者前言
原書前言
縮略語
章緒論1
1.1數論的概念1
1.1節習題8
1.2計算數論的概念10
1.2節習題22
1.3量子計算數論的概念24
1.3節習題27
1.4本章要點及進階閱讀27
參考文獻28
第2章經典計算和量子計算32
2.1經典計算理論32
2.1.1圖靈機32
2.1.2丘奇-圖靈論點35
2.1.3可判定性和可計算性35
2.1節習題36
2.2經典復雜度理論37
2.2.1復雜度分類37
2.2.2Cook-Karp論點40
2.2節習題41
2.3量子信息與量子計算41
2.3節習題45
2.4量子可計算性和量子復雜性47
2.4節習題49
2.5本章要點及進階閱讀51
參考文獻52
第3章分解整數的量子算法55
3.1分解整數的經典算法55
3.1.1基本概念55
3.1.2數域篩法57
3.1.3ρ分解方法67
3.1節習題70
3.2基於整數分解問題的密碼體制73
3.2節習題84
3.3分解整數的Shor算法87
3.3.1量子尋階算法87
3.3.2量子整數分解算法93
3.3.3破解RSA密碼體制的量子算法95
3.3節習題98
3.4量子整數分解算法的其他變體99
3.4節習題106
3.5本章要點及進階閱讀106
參考文獻107
第4章針對離散對數問題的量子計算114
4.1針對離散對數問題的經典算法114
4.1.1基本概念114
4.1.2Shanks的大步小步算法115
4.1.3Silver-Pohlig-Hellman算法118
4.1.4針對離散對數問題的ρ方法123
4.1.5IndexCalculus算法125
4.1.6利用函數域篩法求解小特征域上的離散對數131
4.1節習題135
4.2基於離散對數問題的密碼體制136
4.2.1Diffie-Hellman-Merkle密鑰交換協議137
4.2.2ElGamal密碼體制139
4.2.3Massey-Omura密碼體制141
4.2.4基於離散對數問題的數字簽名143
4.2節習題145
4.3針對離散對數問題的量子算法148
4.3.1基本概念148
4.3.2易解離散對數問題的量子算法150
4.3.3針對一般情形離散對數問題的量子算法152
4.3.4量子離散對數算法的其他變形155
4.3節習題161
4.4本章要點及進階閱讀161
參考文獻163
第5章針對橢圓曲線離散對數問題的量子計算168
5.1求解橢圓曲線離散對數問題的經典算法168
5.1.1基本概念168
5.1.2針對橢圓曲線離散對數問題的Pohlig-Hellman算法168
5.1.3針對橢圓曲線離散對數問題的大步小步算法170
5.1.4針對橢圓曲線離散對數問題的ρ方法171
5.1.5針對橢圓曲線離散對數問題的Xedni方法175
5.1.6橢圓曲線離散對數問題最新進展179
5.1節習題182
5.2基於橢圓曲線離散對數問題的密碼學185
5.2.1基本概念185
5.2.2橢圓曲線密碼學中的預處理186
5.2.3基於橢圓曲線的Diffie-Hellman-Merkle協議187
5.2.4基於橢圓曲線的Massey-Omura協議189
5.2.5基於橢圓曲線的ElGamal密碼192
5.2.6Menezes-Vanstone密碼體制194
5.2.7基於橢圓曲線的數字簽名算法196
5.2節習題197
5.3針對橢圓曲線離散對數問題的量子算法204
5.3.1基本概念204
5.3.2針對橢圓曲線離散對數問題的Eicher-Opoku量子算法208
5.3.3針對橢圓曲線離散對數問題的Proos-Zalka量子攻擊算法211
5.3.4針對ECDLP/ECC量子算法的改進算法213
5.3節習題214
5.4本章要點及進階閱讀215
參考文獻216
第6章針對其他數論難題的量子算法220
6.1求解Pell方程220
6.1節習題226
6.2數論猜想驗證227
6.2.1黎曼猜想驗證227
6.2.2BSD猜想驗證228
6.2節習題230
6.3其他量子算法230
6.4本章要點及進階閱讀232
參考文獻233
內容簡介
本書全面介紹了針對整數分解問題、離散對數問題及橢圓曲線離tfopt數問題的經典及量子算法。同時對經典計算和量子計算中的基本概念及結論進行了介紹，並簡單討論了一些針對其他數論問題和代數問題的量子算法，完備地描述相關數論問題及其密碼應用，簡明扼要地討論了對應經典算法。在量子算法的描述過程中，繫統性強、實例清晰、深人淺出。本書可作為對量子算法、計算數論、抗量子計算密碼感興趣的計算機學者、數學家、電氣工程師及物理學者的參考書，也可作為量子計算數論領域高年級本科生或低年級研究生的教材。
