Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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

Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers

Open access
Ekerå, Martin, Håstad, Johan · 2017 · Lecture Notes in Computer Science

Abstract

We generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekera [2] so as to allow for various tradeoffs between the number of times that the algorithm need be executed on the one hand, and the complexity of the algorithm and the requirements it imposes on the quantum computer on the other hand. Furthermore, we describe applications of algorithms for computing short discrete logarithms. In particular, we show how other important problems such as those of factoring RSA integers and of finding the order of groups under side information may be recast as short discrete logarithm problems. This gives rise to an algorithm for factoring RSA integers that is less complex than Shor’s general factoring algorithm in the sense that it imposes smaller requirements on the quantum computer. In both our algorithm and Shor’s algorithm, the main hurdle is to compute a modular exponentiation in superposition. When factoring an n bit integer, the exponent is of length 2n bits in Shor’s algorithm, compared to slightly more than n/2 bits in our algorithm.

Overview

Integrity signals

Registry

Crossref · 10.1007/978-3-319-59879-6_20

Cites

9 of 9 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Show all 9 references

Cited by

See all 62

Metadata

Authors
Ekerå, M., & Håstad, J.
Affiliations
  • Swedish Armed Forces (SE)
  • KTH Royal Institute of Technology (SE)
Corresponding author
Ekerå, Martin
Venue
Lecture Notes in Computer Science
Published
2017
Pages
347-363
ISSN
  • 0302-9743 (ISSN-L)
  • 1611-3349
OpenAlex
W2594615149
Cited by
62
References
9
Citations by year
2026: 7 · 2025: 16 · 2024: 10 · 2023: 5 · 2022: 8 · 2021: 8 · 2020: 4 · 2019: 2 · 2017: 2
FWCI
1.00
Type
conference paper
Language
en
Open access
Locations
  • Lecture notes in computer science (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
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, Shor's algorithm, side information

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: Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. https://app.cochat.ai/papers/10.1007/978-3-319-59879-6_20
The paper
Ekerå, M., & Håstad, J. (2017). Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-319-59879-6_20

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.