On post-processing in the quantum algorithm for computing short discrete logarithms
On post-processing in the quantum algorithm for computing short discrete logarithms
复制标题
计算短离散对数的量子算法中的后处理
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Martin Ekerå
中科院分区：
文献类型：
--
作者：
Martin Ekerå
我们通过仔细分析算法引起的概率分布来重新审视用于计算短期离散对数的量子算法。 ，我们提出了一种改进的后处理算法，该算法效率更高，可以实现更好的权衡，并需要运行量少于原始的后处理算法，我们通过对量子算法进行了经典的模拟器，通过对其对给定对数产生的概率分布进行采样。 Ekerå -håstad不仅在每个单独的运行中，而且总体上都在针对RSA和DIFFIE -HELLMAN的密码相关实例时，都可以实现比Shor的优势。带有简短的指数。
We revisit the quantum algorithm for computing short discrete logarithms that was recently introduced by Ekerå and Håstad. By carefully analyzing the probability distribution induced by the algorithm, we show its success probability to be higher than previously reported. Inspired by our improved understanding of the distribution, we propose an improved post-processing algorithm that is considerably more efficient, enables better tradeoffs to be achieved, and requires fewer runs, than the original post-processing algorithm. To prove these claims, we construct a classical simulator for the quantum algorithm by sampling the probability distribution it induces for given logarithms. This simulator is in itself a key contribution. We use it to demonstrate that Ekerå–Håstad achieves an advantage over Shor, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie–Hellman with short exponents.