Cédric Pilatte

Fast factoring algorithms

The security of widely used communication systems relies on the presumed difficulty of factoring large integers or computing discrete logarithms. However, Shor’s celebrated algorithm from 1994 demonstrated that quantum computers can perform these tasks in polynomial time. In 2023, Regev proposed an even faster quantum algorithm for factoring integers. Unfortunately, the correctness of his new method is conditional on an ad hoc number-theoretic conjecture. Using tools from analytic number theory, we establish a result in the direction of Regev’s conjecture. This enables us to design an efficient, provably correct quantum algorithm for factoring and solving the discrete logarithm problem. In this talk, we will explore the mathematical ideas behind these developments (requiring no prior knowledge of quantum computing or cryptography).