CoChat
Sign Up
PreprintCited by 9Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCryptography and Residue Arithmetic

The DOI matches its DataCite record; 2 of the 2 references it cites were found in a registry or an index.

Revisiting Shor's quantum algorithm for computing general discrete logarithms

Open access
Ekerå, Martin·2019·arXiv
DOI 10.48550/arxiv.1905.09084arXiv 1905.09084
Open this paper in CoChat — free accountOpen PDF

Abstract

We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order $r$, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as $r \rightarrow \infty$, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm $d$ and $r$ are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if $r$ is known when computing $d$. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1905.09084

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Ekerå and Håstad's derivatives of Shor's algorithms require fewer multiplications than Shor's original algorithms.

    “It is also reduced by using Eker˚ a and H˚ astad's derivatives [21, 23-25] of Shor's algorithms, that require fewer multiplications to be performed compared to Shor's original algorithms.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [21]

    Section 2.1 says tradeoffs in Ekerå–Håstad’s algorithm reduce the quantum group operations needed per run, supporting a qualified version of the claim. But §1.2.5 says Ekerå’s general discrete-logarithm algorithm without tradeoffs requires approximately 3m operations versus 2m for Shor’s; the blanket claim that the derivatives require fewer multiplications is therefore too broad. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Ekerå and Håstad's algorithm factors RSA integers N=pq by computing a short discrete logarithm d = log_g y ≡ p+q (mod r).

    “In [21, 23, 25], Eker˚ a and H˚ astad explain how to factor RSA integers N = pq in a different way; namely by computing a short discrete logarithm.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [21]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 32

  1. Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo- random Bits. SIAM J. Comput. 13(4), pp. 850-864 (1984).
  2. Bourdon, P.S., Williams, H.T.: Sharp probability estimates for Shor's order-finding algo- rithm. Quantum. Inf. Comput. 7(5), pp. 522-550 (2007).
  3. Chevignard, C., Fouque P.-A., Schrottenloher, A.: Reducing the Number of Qubits in Quantum Factoring. In: Proceedings of CRYPTO 2025, Lecture Notes in Comput. Sci. 16001, Springer, Cham, pp. 384-415 (2025).
  4. Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum Algorithms Revisited. Proc. R. Soc. A 454(1969), pp. 339-354 (1998).
  5. Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Trans. Inf. The- ory 22(6), pp. 644-654 (1976).
  6. Ekerå, M., Håstad, J.: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: Proceedings of PQCrypto 2017, Lecture Notes in Comput. Sci. 10346, Springer, Cham, pp. 347-363 (2017).
  7. Ekerå, M.: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1), pp. 359-407 (2021).
  8. Ekerå, M.: On completely factoring any integer efficiently in a single run of an order- finding algorithm. Quantum Inf. Process. 20:205, pp. 1-14 (2021).
  9. Ekerå, M.: On the success probability of quantum order finding. ACM Trans. Quantum Comput. 5(2):11, pp. 1-40 (2024).
  10. Ekerå, M.: On factoring integers, and computing discrete logarithms and orders, quan- tumly. PhD thesis, KTH Royal Institute of Technology (2024).
  11. Ekerå, M.: On the success probability of the quantum algorithm for the short DLP. ArXiv 2309.01754v3 (2025). (See also ArXiv 2309.01754v4 which is to appear.) · arXiv
  12. Griffiths, R.B., Niu, C.-S.: Semiclassical Fourier Transform for Quantum Computation. Phys. Rev. Lett. 76, pp. 3228-3231 (1996).
  13. Kaliski, B.S.: Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools. PhD thesis, MIT (1988).
  14. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), pp. 203-209 (1987).
  15. May, A., Schlieper, L.: Quantum Period Finding is Compression Robust. IACR Trans. Symmetric Cryptol. 2022(1), pp. 183-211 (2022).
  16. Miller, G.L.: Riemann's hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3), pp. 300-317 (1976).
  17. Miller, V.S.: Use of Elliptic Curves in Cryptography. In: Proceedings of CRYPTO 1985, Lecture Notes in Comput. Sci. 218, Springer, Heidelberg, pp. 417-426 (1986).
  18. Mosca, M.: Quantum Computer Algorithms. PhD thesis, University of Oxford, Wolfson College (1999).
  19. Mosca, M., Ekert, A.: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In: Proceeding from the First NASA International Conference, QCQC 1998, Lecture Notes in Comput. Sci. 1509, Springer, Berlin Heidelberg, pp. 174- 188 (1999).
  20. Nemes, G.: Error bounds for the asymptotic expansion of the Hurwitz zeta function. Proc. R. Soc. A. 473(2203):20170363, pp. 1-16 (2017).
  21. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cam- bridge University Press, 10th Anniversary Edition (2010).
  22. van Oorschot, P., Wiener, M.J.: Parallel Collision Search with Cryptanalytic Applications. J. Cryptol. 12(1), pp. 1-28 (1999).
  23. Parker, S., Plenio, M.B.: Efficient Factorization with a Single Pure Qubit and log N Mixed Qubits. Phys. Rev. Lett. 85(14), pp. 3049-3052 (2000).
  24. Pohlig, S., Hellman, M.: An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance. IEEE Trans. Inf. Theory 24(1), pp. 106-110 (1978).
  25. Pollard, J.M.: Monte Carlo Methods for Index Computation (mod p). Math. Comput. 32(143), pp. 918-924 (1978).
  26. Proos, J., Zalka, C.: Shor's discrete logarithm quantum algorithm for elliptic curves. Quan- tum Inf. Comput. 3(4), pp. 317-344 (2003). (Retrieved from the ArXiv, see arXiv:quant- ph/0301141v2).
  27. Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2), pp. 120-126 (1978).
  28. Seifert, J.-P.: Using fewer qubits in Shor's factorization algorithm via simultaneous Dio- phantine approximation. In: CT-RSA, Lecture Notes in Comput. Sci. 2020, Springer, Berlin Heidelberg, pp. 319-327 (2001).
  29. Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposia in Pure Mathematics, vol. 20, pp. 415-440 (1971).
  30. Shor, P.W.: Algorithms for Quantum Computation: Discrete Logarithms and Factor- ing. In: SFCS, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, pp. 124-134 (1994).
  31. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), pp. 1484-1509 (1997).
  32. Zalka, C.: Fast versions of Shor's quantum factoring algorithm. ArXiv quant- ph/9806084v1 (1998).

Cited by

Sorted by citations

Metadata

Authors
Ekerå, M.
Affiliations
Swedish Armed Forces (SE)
Corresponding author
Ekerå, Martin
ORCID
Ekerå, Martin
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1905.09084
arXiv
1905.09084
OpenAlex
W2945624639
Cited by
9
References
2
Citations by year
2025: 2 · 2024: 1 · 2022: 3 · 2020: 3
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Centre for Supercomputing Applications
  • Vetenskapsrådet (05973, 2018-, 201805973)
  • Försvarsmakten
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
Keywords
Shor's algorithm, discrete logarithm problem, quantum algorithms, success probability, classical post-processing, heuristic analysis, group order, quantum algorithm simulation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review