Paper 2018/797

Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

Martin Ekerå

Abstract

We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.

Note: This minor revision primarily explains how orders and/or general discrete logarithms may be efficiently computed in the special case where the group order is partially very smooth. It furthermore (a) accounts for the recent publication of [5] "On completely factoring any integer efficiently in a single run of an order finding algorithm" in appendix A.7, (b) corrects an error in the closed-form expression for the special case where theta_r is zero in appendix A.2.1, (c) requires that 2^(m-1) < r where it was previously required that 2^(m-1) <= r in appendix A.1 step 1, and (d) makes some clarifications in section 7.4. It also adds references to a few additional works, and removes references to works treated in [5] that are now less relevant. No key findings are affected compared to the previous version of the manuscript.