Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Shor's Algorithm and the Unproven Premise: An Assumption Audit of the Quantum Factoring Narrative

QNFO Research, Rowan Brad Quni-Gudzinas

Published Jul 14, 2026• 0 citations
Publisher

Abstract

Systematic audit decomposing Shor's 1994 algorithm into nine assumptions spanning number theory, computational complexity, and quantum physics. The central finding: Shor proved FACTORING ∈ BQP (factoring is in quantum polynomial time), but the claim "quantum computers break RSA" additionally requires FACTORING ∉ BPP — a premise unproven after 30 years. Delivers 17 artifacts: manuscript, Shor-Crossover Simulator (Python + HTML dashboard), policy brief, abelian HSP classification audit, GNFS constant trajectory analysis, NIST PQC narrative analysis, expert survey synthesis, formal claim gap analysis, Shor failure probability bounds, classical ORDER-FINDING analysis, and Knowledge Graph cross-reference against 611 QNFO publications. RSA-2048 requires 2.1-7.9M physical qubits; crossover at ~2040 under optimistic projections.

DOI
10.5281/zenodo.21354770

Related papers

Shor's Algorithm and the Unproven Premise: An Assumption Audit

Rowan Brad Quni-Gudzinas

Shor's 1994 algorithm proves that a quantum Turing machine can factor an n-bit integer using O(n³) gates, establishing FACTORING ∈ BQP. However, the widely propagated claim that this constitutes a "quantum advantage" or that "RSA is broken" requires the additional premise FACTORING ∉ BPP — that no polynomial-time classical factoring algorithm exists. This premise is unproven after 30 years and is equivalent to separating complexity classes (BPP vs. BQP) whose relationship remains open. This paper systematically decomposes Shor's claim architecture into nine assumptions spanning number theory, computational complexity, and quantum physics. We find that while the mathematical core (FACTORING ∈ BQP) is rigorous, the practical interpretation (quantum computers will break cryptography) rests on a chain of contingent assumptions linked by the unproven FACTORING ∉ BPP. Through executable simulation (shor_crossover.py v1.0), an abelian HSP classification audit, a GNFS constant trajectory analysis, a surface code resource model, and a meta-scientific review of NIST PQC documents and expert surveys, we demonstrate that: (1) RSA-2048 requires 2.1–7.9 million physical qubits at 99.9–99.999% gate fidelity, with crossover to quantum advantage occurring ~2040 under optimistic roadmap projections [CODE-EXECUTED]; (2) a significant majority of known exponential quantum speedups (when counted by problem instances solved) reduce to abelian hidden subgroup problem variants [LLM-INFERRED], suggesting quantum advantage is architecturally narrow rather than general; (3) the GNFS complexity constant c ≈ 1.923 has been stable for 30 years with no evidence of a polynomial-time trend [LLM-INFERRED]; (4) NIST PQC documents and expert surveys systematically underrepresent the FACTORING ∉ BPP uncertainty [LLM-INFERRED]. We conclude that Shor's algorithm is better understood as an existence proof that abelian algebraic periodicity is efficiently detectable via quantum interference — a narrow but genuine discovery — rather than as a general proof of quantum computational supremacy. Full text and updates: https://papers.qnfo.org/papers/shor-assumptions-audit/

•Jul 14, 2026•0 citations

How Quantum Computing Breaks RSA? - A Study of Shor's Algorithm

Arnav Jain

The advent of quantum computing poses a fundamental threat to classical cryptographic systems, particularly RSA encryption, which relies on the computational limit of prime factorization. This paper presents a comparative analysis of four integer factorization approaches-a selfcurated brute-force classical implementation, optimized Trial Division, Pollard's Rho algorithm, and Shor's algorithmevaluated across a dataset of increasing semiprime inputs representative of scaled-down RSA encryption keys. Through Python-based implementations and simulations, we empirically measure and plot runtime complexity for classical methods while modeling theoretical runtimes for Shor's algorithm, given hardware limitations. Our findings reveal the exponential scaling limitations of classical algorithms, and contrast them with the polynomial-time behavior of Shor's algorithm. Despite being simulated, Shor's consistently flatter runtime trendline demonstrated its theoretical superiority and the critical urgency of post-quantum cryptography. This study not only visualizes the performance divide between classical and quantum paradigms but also underscores the transformational potential of quantum computing in modern cryptanalysis.

IEEE MIT Undergraduate Research Technology Conference (URTC)•Oct 10, 2025•1 citation

Implementation and Analysis of Shor's Algorithm to Break RSA Cryptosystem Security

Siyon Singh, Eric Sakk

The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.

•Jan 8, 2024•11 citations

Implementation and Analysis of Shor's Algorithm to Break RSA Cryptosystem Security

Siyon Singh, Eric Sakk

The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.

•Dec 14, 2023•1 citation

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

E. Gerjuoy

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.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•101 citations

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.

arXiv:2306.09122•Quanta•Sep 15, 2023•15 citations
Systematic audit decomposing Shor's 1994 algorithm into nine assumptions spanning number theory, computational complexity, and quantum physics. The central finding: Shor proved FACTORING ∈ BQP (factoring is in quantum polynomial time), but the claim "quantum computers break RSA" additionally requires FACTORING ∉ BPP — a premise unproven after 30 years. Delivers 17 artifacts: manuscript, Shor-Crossover Simulator (Python + HTML dashboard), policy brief, abelian HSP classification audit, GNFS constant trajectory analysis, NIST PQC narrative analysis, expert survey synthesis, formal claim gap analysis, Shor failure probability bounds, classical ORDER-FINDING analysis, and Knowledge Graph cross-reference against 611 QNFO publications. RSA-2048 requires 2.1-7.9M physical qubits; crossover at ~2040 under optimistic projections.
Shor's 1994 algorithm proves that a quantum Turing machine can factor an n-bit integer using O(n³) gates, establishing FACTORING ∈ BQP. However, the widely propagated claim that this constitutes a "quantum advantage" or that "RSA is broken" requires the additional premise FACTORING ∉ BPP — that no polynomial-time classical factoring algorithm exists. This premise is unproven after 30 years and is equivalent to separating complexity classes (BPP vs. BQP) whose relationship remains open. This paper systematically decomposes Shor's claim architecture into nine assumptions spanning number theory, computational complexity, and quantum physics. We find that while the mathematical core (FACTORING ∈ BQP) is rigorous, the practical interpretation (quantum computers will break cryptography) rests on a chain of contingent assumptions linked by the unproven FACTORING ∉ BPP. Through executable simulation (shor_crossover.py v1.0), an abelian HSP classification audit, a GNFS constant trajectory analysis, a surface code resource model, and a meta-scientific review of NIST PQC documents and expert surveys, we demonstrate that: (1) RSA-2048 requires 2.1–7.9 million physical qubits at 99.9–99.999% gate fidelity, with crossover to quantum advantage occurring ~2040 under optimistic roadmap projections [CODE-EXECUTED]; (2) a significant majority of known exponential quantum speedups (when counted by problem instances solved) reduce to abelian hidden subgroup problem variants [LLM-INFERRED], suggesting quantum advantage is architecturally narrow rather than general; (3) the GNFS complexity constant c ≈ 1.923 has been stable for 30 years with no evidence of a polynomial-time trend [LLM-INFERRED]; (4) NIST PQC documents and expert surveys systematically underrepresent the FACTORING ∉ BPP uncertainty [LLM-INFERRED]. We conclude that Shor's algorithm is better understood as an existence proof that abelian algebraic periodicity is efficiently detectable via quantum interference — a narrow but genuine discovery — rather than as a general proof of quantum computational supremacy. Full text and updates: https://papers.qnfo.org/papers/shor-assumptions-audit/
The advent of quantum computing poses a fundamental threat to classical cryptographic systems, particularly RSA encryption, which relies on the computational limit of prime factorization. This paper presents a comparative analysis of four integer factorization approaches-a selfcurated brute-force classical implementation, optimized Trial Division, Pollard's Rho algorithm, and Shor's algorithmevaluated across a dataset of increasing semiprime inputs representative of scaled-down RSA encryption keys. Through Python-based implementations and simulations, we empirically measure and plot runtime complexity for classical methods while modeling theoretical runtimes for Shor's algorithm, given hardware limitations. Our findings reveal the exponential scaling limitations of classical algorithms, and contrast them with the polynomial-time behavior of Shor's algorithm. Despite being simulated, Shor's consistently flatter runtime trendline demonstrated its theoretical superiority and the critical urgency of post-quantum cryptography. This study not only visualizes the performance divide between classical and quantum paradigms but also underscores the transformational potential of quantum computing in modern cryptanalysis.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.
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.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.