Abstract

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 the first part of this talk, we will provide an accessible overview of these developments and their place within the broader context of cryptography. The discussion will require no prior background as we will cover the necessary concepts, including a brief introduction to quantum computing from a mathematician’s perspective.

The second part of the talk will focus on the number-theoretic aspects of this work. We will outline the proof of a variant of Regev’s conjecture, using lattice techniques, character sums and zero-density estimates for Dirichlet L-functions.