On factoring RSA integers and computing discrete logarithms on quantum computers

by Martin Ekerå (KTH)

Wednesday 4 Mar 2020, 13:00 → 14:00 Europe/Stockholm

112:028 (Nordita south)

In this talk, we give an overview of the state of factoring integers and computing discrete logarithms on quantum computers, focusing on algorithms that have been demonstrated to be polynomial time. More specifically, we treat Shor's algorithms for the IFP, OFP and DLP, Seifert's algorithm for the IFP and OFP with tradeoffs, and our algorithms for the short DLP, DLP and RSA IFP, with or without tradeoffs.

We quantify the cost reductions we obtain, both in the logical circuit model, and in a full stack implementation modelled upon existing superconducting quantum computing architectures. The full stack cost estimates are a joint work with Craig Gidney at Google Quantum AI.

We provide tight analyses of the success probabilities of the aforementioned algorithms, classical simulators for the algorithms, and efficient lattice-based post-processing. We show that our algorithms outperform Shor's and Seifert's algorithms for the short DLP and the RSA IFP.