Welcome to the resource topic for 2024/629
Title:
Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
Authors: Cédric Pilatte
Abstract:In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in (\mathbb{Z}/N\mathbb{Z})^{\times} that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
ePrint: https://eprint.iacr.org/2024/629
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .