17、量子计算在椭圆曲线离散对数及佩尔方程求解中的应用

量子计算在椭圆曲线离散对数及佩尔方程求解中的应用

椭圆曲线离散对数问题的量子算法

在密码学领域，椭圆曲线离散对数问题（ECDLP）是构建安全加密系统的重要基础。但随着量子计算技术的发展，传统基于ECDLP的加密系统面临着新的挑战。

Proos - Zalka的ECDLP量子算法

Proos和Zalka提出了一种针对有限域$F_p$（$p$为素数）上ECDLP问题的量子算法。与整数分解问题（IFP）相比，在量子计算环境下，基于ECDLP的加密系统更容易被破解。例如，一个160位的椭圆曲线密码（ECC）密钥在约1000个量子比特的量子计算机上就可能被破解，而分解安全等效的1024位RSA模数则需要约2000个量子比特。

在经典计算中，ECC使用比RSA更小的密钥就能提供相同级别的安全性。但在量子计算中，情况则完全相反。Proos - Zalka对Shor的离散对数量子算法进行了修改，具体如下：
1.替换量子傅里叶变换：将量子傅里叶变换$A_q$替换为$A_{2^n}$（$q \approx 2^n$），以方便实现。
2.消除输入寄存器：只需要一个累加器寄存器来将固定点$P_i$（相对于$Q_i$）添加到点的叠加态（称为群移位），并需要两个幺正变换$U_{P_i}$和$U_{Q_i}$，它们作用于表示椭圆曲线$E$上点的任何基态$|S\rangle$：
- $U_{P_i} : |S\rangle \to |S + P_i\rangle$
- $U_{Q_i} : |S\rangle \to |S + Q_i\rangle$
3.