Cryptography, quantum computers and analytic number theory

Add to your list(s) Download to your calendar using vCal

• Cédric Pilatte (University of Oxford)
• Wednesday 05 February 2025, 13:30-15:00
• MR4, CMS.

If you have a question about this talk, please contact Julia Wolf.

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.

This talk is part of the Discrete Analysis Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Discrete Analysis Seminar
• Hanchen DaDaDash
• Interested Talks
• MR4, CMS
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.