量子计算数论

本书全面介绍了针对整数分解问题、离散对数问题及椭圆曲线离tfopt数问题的经典及量子算法。同时对经典计算和量子计算中的基本概念及结论进行了介绍，并简单讨论了一些针对其他数论问题和代数问题的量子算法，完备地描述相关数论问题及其密码应用，简明扼要地讨论了对应经典算法。在量子算法的描述过程中，系统性强、实例清晰、深人浅出。本书可作为对量子算法、计算数论、抗量子计算密码感兴趣的计算机学者、数学家、电气工程师及物理学者的参考书，也可作为量子计算数论领域高年级本科生或低年级研究生的教材。

《信息科学技术学术著作丛书》序
译者前言
原书前言
缩略语
第1章绪论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