第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.2 Cook-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.2 Shanks的大步小步算法 115
4.1.3 Silver-Pohlig-Hellman算法 118
4.1.4针对离散对数问题的ρ方法 123
4.1.5 Index Calculus算法 125
4.1.6利用函数域筛法求解小特征域上的离散对数 131
4.1节习题 135
4.2基于离散对数问题的密码体制 136
4.2.1 Diffe-Hellman-Merkle密钥交换协议 137
4.2.2 ElGamal密码体制 139
4.2.3 Massey-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.6 Menezes-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.2 BSD猜想验证 228
6.2节习题 230
6.3其他量子算法 230
6.4本章要点及进阶阅读 232
参考文献 233