On the success probability of the quantum algorithm for the short DLP

Ekerå and Håstad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Ekerå–Håstad's algorithm solves the short DLP in groups of unknown order. In this work, we prove a lower bound on the probability of Ekerå–Håstad's algorithm recovering the short logarithm d in a single run. By our bound, the success probability can easily be pushed as high as 1 − 10 − 10 for any short d . A key to achieving such a high success probability is to efficiently perform a limited search in the classical post-processing by leveraging meet-in-the-middle or random-walk techniques. These techniques may be generalized to speed up other related classical post-processing algorithms. Asymptotically, in the limit as the bit length m of d tends to infinity, the success probability tends to one if the limits on the search space are parameterized in m . Our results are directly applicable to Diffie–Hellman in safe-prime groups with short exponents, and to RSA via a reduction from the RSA integer factoring problem (IFP) to the short DLP.