Paper 2016/1128

Modifying Shor’s algorithm to compute short discrete logarithms

Martin Ekerå

Abstract

We revisit Shor's algorithm for computing discrete logarithms in the multiplicative group of GF(p) on a quantum computer and modify it to compute logarithms d in groups <g> of prime order q in the special case where d <<< q. As a stepping stone to performing this modification, we first introduce a modified algorithm for computing logarithms on the general interval 0 < d < q for comparison. We demonstrate conservative lower bounds on the success probability of our algorithms in both the general and the special case. In both cases, our algorithms initially set the index registers to a uniform superposition of all states, compared to p-1 states in Shor's original algorithm. In the special case where d <<< q, our algorithm uses 3 ceil(log d) qubits for the two index registers and computes two QFTs of size 2^(ceil(log d)) and 2^(2 ceil(log d)), compared to 2 floor(log q) qubits for the index registers and two QFTs both of size 2^(floor(log q)) in the general case. A quantum circuit for computing [a - bd] g is furthermore required, where 0 <= a < 2^(2 ceil(log d)) and 0 <= b < 2^(ceil(log d)) in the special case, compared to 0 <= a, b < 2^(floor(log q)) in the general case. This implies that the complexity of computing discrete logarithms on a quantum computer can be made to depend not only on the choice of group, and on its order q, but also on the logarithm d. In the special case where d <<< q, our algorithm does not require q to be prime. It may hence be generalized to finite abelian groups.

Note: The introduction has been updated, two minor typos have been corrected, further references have been added, and we note explicitly that the algorithm may be generalized to finite abelian groups.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
quantum cryptographydiscrete logarithm problemdomain parameterskey exchangeelliptic curve cryptosystemShor's algorithmDiffie-Hellman
Contact author(s)
ekera @ kth se
History
2016-12-07: received
Short URL
https://ia.cr/2016/1128
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1128,
      author = {Martin Ekerå},
      title = {Modifying Shor’s algorithm to compute short discrete logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1128},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1128}},
      url = {https://eprint.iacr.org/2016/1128}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.