The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
On post-processing in the quantum algorithm for computing short discrete logarithms
Open accessAbstract
We revisit the quantum algorithm for computing short discrete logarithms that was recently introduced by Ekerå and Håstad. By carefully analyzing the probability distribution induced by the algorithm, we show its success probability to be higher than previously reported. Inspired by our improved understanding of the distribution, we propose an improved post-processing algorithm that is considerably more efficient, enables better tradeoffs to be achieved, and requires fewer runs, than the original post-processing algorithm. To prove these claims, we construct a classical simulator for the quantum algorithm by sampling the probability distribution it induces for given logarithms. This simulator is in itself a key contribution. We use it to demonstrate that Ekerå–Håstad achieves an advantage over Shor, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie–Hellman with short exponents.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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 [23]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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 [23]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“The total exponent length is hence n e = 3 m = 1 . 5 n + O (1) qubits, compared to 2 n qubits in Shor's algorithm.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [23]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“To compute short logarithms in safe-prime groups, the best option is to use Eker˚ a-H˚ astad's algorithm [23, 25] that is specialized for this purpose.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [23]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“As is explained in [23, 24], a single correct run of these quantum algorithms suffices for the logarithm to be recovered with ≥ 99% success probability in the classical post-processing.”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [23]
Experimental — accuracy not yet measured
4 more claims about this paper
Create a free account to see every claim other papers make about this one.
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
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Factoring polynomials with rational coefficients
Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982) · Mathematische Annalen · doi:10.1007/bf01457454 · Cited by 4,018
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 1×
“To understand why physical qubits may be saved, note that quantum error correcting codes, such as the surface code (see [6] for a good overview), use an array of physical qubits to construct each logical qubit.”
BackgroundLattice basis reduction: Improved practical algorithms and solving subset sum problems
Schnorr, C. P., & Euchner, M. (1994) · Mathematical Programming · doi:10.1007/bf01581144 · Cited by 1,427
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938 · cited 8×
“Mapping v to the closest vector in L using Babai’s [1] nearest plane algorithm is then sufficient to immediately recover u and d without having to enumerate the lattice.”
MethodInfluentialA hierarchy of polynomial time lattice basis reduction algorithms
Schnorr, C. P. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90064-8 · Cited by 648
Über die Classenzahl quadratischer Zahlkörper
Siegel, C. (1935) · Acta Arithmetica · doi:10.4064/aa-1-1-83-86 · Cited by 276
The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer
Mosca, M., & EKERT, A. K. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49208-9_15 · Cited by 179 · cited 1×
“This is because control qubits can be recycled [10,11] in implementations.”
Background
Research works printed but not linked: 1
- Shor P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: SFCS. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society, Washington DC (1994).
Cited by
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Self-citationAn Efficient Quantum Factoring Algorithm
Regev, O. (2025) · Journal of the ACM · doi:10.1145/3708471 · Cited by 42
“The idea of reducing the cost of the quantum circuit at the expense of applying it several times independently and classically post-processing the outputs was already suggested by Seifert [22] (see also [7, 8]).”
Quantum algorithms for typical hard problems: a perspective of cryptanalysis
Suo, J., Wang, L., Yang, S., Zheng, W., & Zhang, J. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02673-x · Cited by 43
Large-Scale Simulation of Shor’s Quantum Factoring Algorithm
Willsch, D., Willsch, M., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2023) · Mathematics · doi:10.3390/math11194222 · Cited by 50
Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptography
Biasse, J., Bonnetain, X., Kirshanova, E., Schrottenloher, A., & Song, F. (2022) · IET Information Security · doi:10.1049/ise2.12081 · Cited by 23
“…≥ 1 the tradeoff factor, the algorithm first induces the state and then applies QFT 2 ν and QFT 2 ℓ to the first and second control registers, respectively, to obtain The probability of observing ( j, k ) and g e for e = a − bd is then [30], Section 3], for b 0 ( e ) and b 1 ( e ) as given in [Ref.”
BackgroundMethodInfluential
Metadata
- Authors
- Ekerå, M.
- Affiliations
- Swedish Armed Forces (SE)
- Corresponding author
- Ekerå, Martin
- ORCID
- Ekerå, Martin
- Venue
- Designs, Codes and Cryptography
- Published
- 2020-08-06
- Volume
- 88
- Issue
- 11
- Pages
- 2313-2335
- ISSN
- 0925-1022 (ISSN-L)
- 1573-7586
- OpenAlex
- W2795035933
- Cited by
- 23
- References
- 17
- Citations by year
- 2026: 2 · 2025: 6 · 2024: 3 · 2023: 2 · 2022: 3 · 2021: 4 · 2020: 2
- FWCI
- 1.08
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Designs Codes and Cryptography (publishedVersion, cc-by)
- IACR Cryptology ePrint Archive (submittedVersion)
- Funders
- Swedish NCSA, Swedish Armed Forces (Not applicable)
- 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
- quantum algorithms, post-processing, success probability, Shor's algorithm, Diffie-Hellman, cryptanalysis
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On post-processing in the quantum algorithm for computing short discrete logarithms. https://app.cochat.ai/papers/10.1007/s10623-020-00783-2
- The paper
- Ekerå, M. (2020). On post-processing in the quantum algorithm for computing short discrete logarithms. Designs, Codes and Cryptography. https://doi.org/10.1007/s10623-020-00783-2
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.

