13、离散对数问题的量子算法探索
离散对数问题的量子算法探索
1. 离散对数问题基础
对数由苏格兰数学家约翰·纳皮尔（John Napier，1550 - 1617）发明，本质上是指数运算的逆运算。若(y = x^k)（(x,y,k \in R)），则(k)是(y)以(x)为底的对数，记为(k = \log_x y)。对数问题（LP）即给定(x)和(y)求(k)，这是个简单问题，可通过以下公式求解：
(\log_x y = \frac{\ln y}{\ln x})，其中(\ln x = \sum_{i = 1}^{\infty} (-1)^{i + 1} \frac{(x - 1)^i}{i})。
例如，(\log_2 5 = \frac{\ln 5}{\ln 2} \approx \frac{1.609437912}{0.692147106} \approx 2.321928095)。
但离散对数问题（DLP）则截然不同，例如在(Z_p^*)而非(R)上的DLP，它是一个难以解决的计算数论问题，可用于构建各种公钥密码系统和协议。常见的经典解决方法有：
1. 小步大步法（Baby - step giant - step）
2. Pollard的(\rho)方法
3. Pollard的(\lambda)方法
4. Pohlig - Hellman方法
5. 指标计算法（如NFS）
6. Xedni计算法
7. 函数域筛法（FFS）
有趣的是，对于整数分解问题（IFP）和DLP，非量子计算机没有已知的高效算法，但量子计算机有。而且一个问题的算法常可应用到另一个问题上，使IFP和DLP成为“姐妹问题”。