对数的

论计算短离散对数的量子算法中的后处理

摘要 我们重新审视了 Ekerå 和 Håstad 最近提出的用于计算短离散对数的量子算法。通过仔细分析该算法引起的概率分布，我们发现其成功概率高于以前报告的概率。受对分布理解的加深的启发，我们提出了一种改进的后处理算法，该算法比原始后处理算法效率更高、能够实现更好的权衡并且需要的运行次数更少。为了证明这些说法，我们通过对给定对数引起的概率分布进行采样，为该量子算法构建了一个经典模拟器。这个模拟器本身就是一项重要贡献。我们用它来证明，在针对具有短指数的 RSA 和 Diffie–Hellman 的加密相关实例时，Ekerå–Håstad 不仅在每次单独运行中，而且在整体上都比 Shor 更具优势。