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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemfactoringRSAShor's algorithms
Contact author(s)
ekera @ kth se
History
2020-09-17: last of 3 revisions
2018-09-01: received
See all versions
Short URL
https://ia.cr/2018/797
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/797,
      author = {Martin Ekerå},
      title = {Quantum algorithms for computing general discrete logarithms and orders with tradeoffs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/797},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/797}},
      url = {https://eprint.iacr.org/2018/797}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.