On the state of the art of factoring integers and computing discrete logarithms quantumly

Abstract: 
We provide a high-level overview of the state of the art of factoring integers and computing discrete logarithms on future large-scale fault-tolerant quantum computers — as they are currently envisaged. 

More specifically, we review the state-of-the-art quantum algorithms for solving the RSA integer factoring problem (IFP), the short discrete logarithm problem (DLP) in cyclic groups of unknown order, and the general DLP in cyclic groups of known or unknown order. These problems are of immediate cryptologic relevance: They underpin virtually all currently widely deployed asymmetric cryptology, including but not limited to RSA, (EC-)DH, and (EC-)DSA. For completeness, we also review the state-of-the-art quantum algorithms for the general IFP and for the general order-finding problem (OFP).

Shor first published his groundbreaking algorithms back in 1994. Since then, several variations of the original algorithms have been entered into the literature, including but not limited to Seifert's variation for the OFP, our variations for the RSA IFP, short DLP and general DLP, Regev's fairly recent d-dimensional variation for the general IFP, and our very recent extension of Regev's variation to the general DLP and OFP. Furthermore, there has been much work on optimizations to enable efficient implementation, post-processing and simulation. The aim of this talk is to paint a picture of the current algorithmic landscape in broad strokes.