Paper 2018/797

Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

Martin Ekerå

Abstract

In this paper, we generalize and bridge Shor's groundbreaking works on computing orders and general discrete logarithms, our earlier works on computing short discrete logarithms with tradeoffs and Seifert's work on computing orders with tradeoffs. In particular, we demonstrate how the idea of enabling tradeoffs may be extended to the case of computing general discrete logarithms. This yields a reduction by up to a factor of two in the number of group operations that need to be computed in each run of the quantum algorithm at the expense of having to run the algorithm multiple times. Combined with our earlier works this implies that the number of group operations that need to be computed in each run of the quantum algorithm equals the number of bits in the logarithm times a small constant factor that depends on the tradeoff factor. We comprehensively analyze the probability distribution induced by our quantum algorithm, describe how the algorithm may be simulated, and estimate the number of runs required to compute logarithms with a given minimum success probability for different tradeoff factors. Our algorithm does not require the group order to be known. If the order is unknown, it may be computed at no additional quantum cost from the same set of outputs as is used to compute the logarithm.