Date
Mon, 27 Jan 2025
16:00
Location
C4
Speaker
Cédric Pilatte
Organisation
University of Oxford

The security of many widely used communication systems hinges on the presumed difficulty of factoring 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 a provably correct quantum algorithm for factoring and solving the discrete logarithm problem, whose efficiency is comparable to Regev's approach. In this talk, we will give an accessible account of these developments.

Last updated on 24 Jan 2025, 3:39pm. Please contact us with feedback and comments about this page.