CoChat
Sign Up
Cited by 76Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCryptography and Residue Arithmetic

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

Open access
Gerjuoy, Edward·2005·American Journal of Physics
DOI 10.1119/1.1891170
Open this paper in CoChat — free accountOpen PDF

Abstract

The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

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

Crossref · 10.1119/1.1891170

Cites

10 of 10 references verified0 citation errors · 0 not checkable

Statistics

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?

  • ML-KEM security relies on the Module Learning-with-Errors problem, for which there is no known polynomial-time quantum algorithm.

    “its security relies on the Module Learningwith-Errors (M-LWE) problem, for which there is no known polynomial-time quantum algorithm [56,57].”

    From A hybrid encryption algorithm based on AES and Kyber for secure image protection in the post-quantum era (2026) · cites this paper as [57]

    The Introduction (p. 1) says the paper addresses RSA and Shor’s factoring algorithm, with other aspects of quantum cryptography and computation beyond its scope. Searches for ML-KEM, Module Learning-with-Errors, and a polynomial-time quantum algorithm for that problem found no passage addressing either part of the claim. (LLM, conf=0.78)

    Experimental — accuracy not yet measured

Self-check

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

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

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Gerjuoy, E.
Affiliations
University of Pittsburgh (US)
Corresponding author
Gerjuoy, Edward
Venue
American Journal of Physics
Publisher
American Association of Physics Teachers (AAPT)
Published
2005-05-13
Volume
73
Issue
6
Pages
521-540
ISSN
  • 0002-9505 (ISSN-L)
  • 1943-2909
DOI
10.1119/1.1891170
OpenAlex
W2117231715
Cited by
76
References
10
Citations by year
2026: 8 · 2025: 9 · 2024: 5 · 2023: 8 · 2022: 5 · 2021: 4 · 2020: 3 · 2019: 1 · 2018: 2 · 2017: 1 · 2013: 2 · 2012: 1
FWCI
2.82
Type
journal article
Language
en
Open access
Locations
  • American Journal of Physics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
Keywords
Shor's algorithm, quantum computing, integer factorization, RSA encryption, public-key cryptography, computational effort, success probability

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