Paper 2024/629
Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- factoringquantumnumber theorylatticesGeneralized Riemann Hypothesis
- Contact author(s)
- cedric pilatte @ maths ox ac uk
- History
- 2024-04-26: approved
- 2024-04-24: received
- See all versions
- Short URL
- https://ia.cr/2024/629
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2024/629, author = {Cédric Pilatte}, title = {Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/629}, year = {2024}, url = {https://eprint.iacr.org/2024/629} }