Pith. sign in

REVIEW 3 major objections 4 minor 34 references

Building Shor's Algorithm in Lean: An Agentic Formalization of Quantum Attacks on RSA-2048 and P-256

T0 review · 3 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A machine-checked formalization aims to certify concrete quantum attack costs for RSA-2048 and P-256, with success probability at least 2/3 and explicit logical resource counts, while openly marking the final numbers as supplied certificate

desk verdict A substantial but overclaimed formalization: the terminal theorems assume the resource counts and success probabilities they claim to prove. read the letter →

arxiv 2607.14082 v1 pith:YBZFVBHS submitted 2026-07-15 quant-ph

Lei Zhang , Yusheng Zhao , Hongshun Yao , Xin Wang This is my paper
classification quant-ph MSC 68Q1281P6811Y0514H52 PACS 03.67.Ac03.67.Lx
keywords Shor'salgorithmRSA-2048factorizationP-256elliptic-curvediscretelogarithmformalverificationmachine-checkedproofquantumresourceestimationreversiblearithmeticorderfinding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that a machine-checked proof environment can package the mathematical core of Shor's algorithm — order finding, reversible modular arithmetic, elliptic-curve scalar multiplication, and classical recovery — into formal theorems with quantitative success probabilities and logical resource counts for RSA-2048 and P-256. Its two central theorems assert that quantum algorithms exist to factor RSA-2048 or recover the P-256 private scalar with probability at least 2/3 at stated qubit, Toffoli, and depth levels. The theorems are honest about their own boundaries: the resource equalities and success bounds enter as explicit certificate fields, and the text says deriving them from a full circuit execution remains open. A sympathetic reader should take the contribution as a reusable formal skeleton with clearly marked assumptions, not as a complete end-to-end proof of the attack costs.

What carries the argument

The central mechanism is the certificate boundary: terminal theorems consume witness objects whose fields include resource equalities (such as qubit count 6190, Toffoli count 8.1e9, or 126e9) and readiness flags, and the proof checks only the logical consequences of those fields. Underneath, typed circuit objects with correctness lemmas and resource projections carry the algebra of reversible modular arithmetic and elliptic-curve operations. The agentic formalization workflow — agents drafting proofs, human review, machine checking — is what lets the project assemble these layers into two public propositions.

What would settle it

Set the certificate field for the Toffoli count in the terminal P-256 proposition to a different value, say 1 instead of 126,000,000,000, and rerun the checker; if the same proof still typechecks, the resource number is not enforced by the formal development, confirming that the theorems assume rather than derive the quoted costs.

Watch

Extended reading notes

Core claim

The discovery is that the two attack routes can be decomposed into reusable formal layers — number-theoretic reductions, reversible arithmetic circuits, probability bounds, and resource accounting — and then reassembled into application-level theorems whose success and resource numbers are recorded as inspectable certificate fields. Theorem 1 asserts an algorithm returning a nontrivial factor of an RSA-2048 modulus with probability at least 2/3 using 6.19e3 logical qubits, 8.1e9 Toffoli gates, 6.42e9 circuit depth, and 36,906 classical operations. Theorem 2 asserts scalar recovery on P-256 with probability at least 2/3 using 2.33e3 logical qubits, 1.26e11 Toffoli gates, 1.16e11 depth, and 7

Load-bearing premise

The paper's central results stand only if the certificate fields — resource numbers, success probabilities, and readiness flags — are genuine, eventually derivable facts; if they are placeholders, the theorems merely describe what would follow from assumed data.

Editorial extensions

If this is right

  • If the certificates are eventually derived from circuit executions, the same repository would supply machine-checked end-to-end resource statements for Shor-type attacks on RSA-2048 and P-256.
  • The three-trial accounting shows success probability at least 2/3 follows from per-attempt failure probability at most 1/2; any source supplying a per-run success bound can be plugged into the same theorem.
  • The reversible modular and prime-field arithmetic layers are reusable for other quantum arithmetic or cryptanalytic analyses.
  • The P-256 statement, with its generic cyclic-group recovery branch and curve arithmetic, can be adapted to other standardized curves by replacing the domain-parameter hypotheses.
  • Resource comparisons across quantum-cryptanalysis estimates become auditable: the formal statements expose exactly which numbers are assumed and which relations are proved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The terminal theorems currently certify implications of assumed resource data, not the resource data itself; changing a certificate field would leave the proof valid, so the numerical headline should be read as literature-sourced, not machine-derived.
  • Closing the integration gap would require deriving the success bound and gate counts from the actual formalized circuits; that is the testable next step and would turn the conditional theorems into unconditional ones.
  • The certificate pattern could be adopted for other quantum resource estimates, but it also means two formalizations with different certificate values could both check while disagreeing on costs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper reports a Lean formalization, produced with agentic proof development, of mathematical and circuit layers intended to support Shor-type quantum attacks on RSA-2048 and on the elliptic curve P-256. Its headline results, Theorem 1 and Theorem 2, assert the existence of quantum algorithms that recover a prime factor or the private scalar with probability at least 2/3 at stated logical resource counts. The formalization covers order finding, reversible modular arithmetic, finite-group discrete-logarithm reductions, reversible prime-field and elliptic-curve operations, and classical recovery, with the final application statements assembled from circuit lemmas, probability certificates, and resource records imported from the literature.

Significance. The paper has real strengths: it describes a substantial machine-checked library of local circuit semantics, cleanup properties, reversible arithmetic, and probability and recovery statements, and it is unusually explicit about the certificate boundaries between proved circuit facts and imported resource/success data. If the endpoint theorems were fully derived from constructed circuits, this would be a notable step toward machine-checked quantum cryptanalysis. However, the central existence claims are not established as stated: the resource values and success probabilities in Theorems 1 and 2 are supplied as certificate fields and hypotheses, not derived from a circuit run, and the paper itself repeatedly concedes that the derivations remain open. The contribution is therefore a documented formal infrastructure plus a conditional specification, rather than a proof of the advertised quantum attacks.

major comments (3)
  1. [§4.3, Theorem 1, Listing 3] Theorem 1 is not established. The one-half per-attempt failure bound is assumed, not derived; §4.3 states that deriving it 'requires an explicit number of order-finding samples and would increase the quantum cost.' It also states that the success figure and the resource tuple 'summarize different calculations' and that a complete analysis must establish both. Listing 3 confirms the gap: logicalQubits = 6190, toffoliGates = ... and readyForFinalStatement are fields/conjuncts of the existential proposition, i.e., supplied inputs, not conclusions from a constructed circuit. Thus the theorem is conditional on certificates whose existence is not proved.
  2. [§5.4, Theorem 2, Listing 4] Theorem 2 has the same structural defect. §5.4 explicitly says 'the measurement weights and resource equalities enter as separate premises' and that an execution from public curve data 'remains an integration task.' Listing 4 shows resources.logicalQubits = 2330, toffoliGates = 126000000000, maximalToffoliDepth = 116000000000, and readyForFinalStatement = true as fields of the existential witness. The probability-at-least-2/3 bound rests on supplied outcome weights, not on analysis of the measurement distribution of the constructed circuit. Consequently the asserted existence of a P-256 scalar-recovery algorithm with these resources is unsupported.
  3. [§6 (conclusion) and §B.4] The manuscript's own conclusion states that 'A complete execution beginning from a 2048-bit modulus or a P-256 public point remains to be constructed for each application.' This directly contradicts the plain reading of Theorems 1 and 2 as existence theorems for algorithms whose input is the public modulus or the public curve data. The main-text theorems and Tables 1–2 need to be restated with the certificate assumptions made explicit, or replaced by the conditional statements that the formal development actually proves.
minor comments (4)
  1. [§2.1 and §4.3] The RSA-2048 theorem calls 6.42e9 a 'maximal circuit depth,' while §4.3 notes that the source reports 'measurement depth' and that relating the two 'requires an additional argument.' The terminology should be corrected or the caveat should appear with Theorem 1.
  2. [Table 3 and §3.2] The table gives a full check for 'Lean (Ours)' in all categories, but §3.2 states that at the terminal RSA-2048 statement the success bound and resource tuple 'enter through separate certificates.' The table should use partial marks or a footnote for the endpoint layer to avoid overstating coverage.
  3. [§B.3, Listing 4] Listing 4's fields such as w.resources.readyForFinalStatement = true are readability flags. It would help to clarify in the text that these are certificate inputs, not derived facts about the circuit, and that 'ready' means the record has been supplied.
  4. [§1 and §3.1] The abstract says the paper 'formalize[s] the logical resource estimates,' but the body shows the estimates are imported and only locally connected. Consider using 'formally records with explicit certificate boundaries' or similar.

Circularity Check

3 steps flagged · score 8.0 of 10

Theorems 1–2 assert existence of concrete quantum algorithms, but the Lean endpoints quantify over witnesses/certificates whose fields already contain the resource counts, success weights, and readiness flags; the paper itself concedes the required derivations remain open.

  1. self definitional [§B.2 Listing 3; Theorem 1; §4.3]
    "finalSuccessAccountedEnvelope.fields.logicalQubits = 6190 ∧ finalSuccessAccountedEnvelope.fields.toffoliGates = retry.runCount * 2700000000 ∧ finalSuccessAccountedEnvelope.fields.circuitDepth = retry.runCount * 2140000000 ∧ classicalArithmeticOps = 36906 ∧ retry.readyForFinalStatement = true ∧ finalSuccessAccountedEnvelope.readyForFinalStatement = true"

    The proposition presented as the RSA-2048 public theorem is PublicTheoremShape built over an InputClass, and these numeric equalities are conjuncts about fields of finalSuccessAccountedEnvelope and retry, not conclusions computed from a circuit. The paper says in §4.3 that deriving the 36,906 budget from Algorithm 3 remains open, that deriving the assumed one-half failure rate from the one-sample bound remains open, and that calling the tripled value a maximal circuit depth requires an additional argument. Therefore the existence claim in Theorem 1 — a quantum algorithm with these resources and probability at least 2/3 — reduces, by construction, to the existence of a supplied input certificate carrying these same numbers; the resource profile is an assumed field, not a derived prediction.

  2. self definitional [§B.3 Listing 4; Theorem 2; §5.4]
    "w.resources.logicalQubits = 2330 ∧ w.resources.toffoliGates = 126000000000 ∧ w.resources.maximalToffoliDepth = 116000000000 ∧ w.resources.classicalOps = 7 ∧ w.resources.toffoliRunMultiplier = 1 ∧ w.resources.depthRunMultiplier = 1 ∧ w.resources.readyForFinalStatement = true"

    PublicTheoremShape for P-256 is ∃ witness, PublicEndpointWitness.Statement I witness, and Statement contains w.output = I.privateScalar.value, the 2/3 success inequality, and these resource equalities as conjuncts over fields of the witness. §5.4 states: 'In the current proof route, the measurement weights and resource equalities enter as separate premises,' and 'An execution that receives only the public curve data and computes m remains an integration task.' Thus Theorem 2's asserted existence of an algorithm with 2.33×10^3 qubits, 1.26×10^11 Toffoli gates, and probability at least 2/3 is equivalent to an existential over a supplied witness whose fields already contain those values; no circuit execution derives them.

1 more flagged steps
  1. fitted input called prediction [§4.3 Ekerå–Håstad route, RSA success probability]
    "The success figure used here assumes that each factoring attempt fails with probability at most one half and that three attempts are independent. Their joint failure probability is then at most 1/8 ≤ 1/3, giving success probability at least 2/3. Deriving the assumed one-half rate from the one-sample bound above requires an explicit number of order-finding samples and would increase the quantum cost."

    The probability at least 2/3 claimed in Theorem 1 is arithmetically forced by the assumed per-attempt failure probability of at most one half, which the paper explicitly says is not derived from the formalized one-sample bound. The repeated-trial calculation only combines an assumed constant; the success threshold is an input premise relabeled as the theorem's quantitative guarantee.

full rationale

The paper contains substantial local formalization: modular addition semantics, controlled exponentiation, field arithmetic, and recovery lemmas are real checked components, and those are not circular. The circularity sits at the application layer, where the terminal theorems are assembled. The paper's own limitation statements make this explicit: §4.3 says deriving the one-half failure rate from the one-sample bound remains open, that deriving the classical-operation budget from Algorithm 3 remains open, and that calling the measurement depth a maximal circuit depth requires an additional argument; §5.4 says the measurement weights and resource equalities enter as separate premises and that an execution from public curve data remains an integration task; §6 says the final RSA-2048 and P-256 propositions begin with recovered outputs, probability bounds, and resource equalities as assumptions. Listings 3 and 4 make the reduction concrete: the target numbers and readyForFinalStatement flags are conjuncts over envelope/witness fields, and the P-256 theorem is literally an existential over such a witness. Consequently, Theorems 1 and 2 as prose existence claims do not follow from a constructed circuit; they restate what would follow from supplied certificates. The self-citations in the paper ([17], [20]) are not the load-bearing problem here; the problem is that the central predicted quantities are inputs to the terminal propositions. A score of 8 reflects that the central claims reduce by construction to supplied fields, even though many intermediate formal results have independent content.

Assumptions & free parameters 7 free parameters · 6 assumptions · 0 invented entities

The central claims rest on imported resource values, assumed failure rates, and formal certificate fields; the paper's own limitations section calls these 'explicit assumptions.' No new physical entities are introduced.

free parameters (7)
  • RSA-2048 logical qubit count = 6190
    Imported from Gidney–Ekerå [21] and asserted as an equality in the terminal Lean proposition (Listing 3); no formal derivation from circuit to this count is provided.
  • RSA-2048 Toffoli-gate total = 8.1e9 (2.7e9 × 3)
    One-run value imported from [21], tripled for three attempts; asserted in Theorem 1 and Listing 3 without deriving it from a formal circuit execution.
  • RSA-2048 circuit depth = 6.42e9 (2.14e9 × 3)
    Source reports measurement depth; the theorem labels it 'maximal circuit depth' and §4.3 says relating the two quantities requires an additional argument.
  • RSA-2048 classical operations = 36,906
    Stated as a budget; §4.3 says 'deriving that budget from Algorithm 3 remains open.'
  • P-256 resource tuple = 2,330 qubits; 1.26e11 Toffoli; 1.16e11 depth; 7 classical ops
    Imported from [7] plus local classical bookkeeping; asserted as `w.resources.*` equalities in Listing 4.
  • Per-attempt failure probability = ≤ 1/2
    Assumed to derive the ≥2/3 three-trial bound; §4.3 says deriving this rate requires an explicit number of order-finding samples and would increase the quantum cost.
  • P-256 success weight = ≥ 2/3
    Measurement outcome weights are supplied separately (§5.4); not derived from measurement of the concrete circuit.
assumptions (6)
  • standard math Standard Mathlib/Lean-QIT foundations are sound and applicable
    Relies on Mathlib, CSLib, and Lean-QIT as imported formal infrastructure; reasonable background.
  • domain assumption NIST P-256 domain parameters satisfy the stated field, curve, and subgroup properties
    §5.4: formalization 'takes as hypotheses the field, curve, and subgroup properties of these constants.'
  • domain assumption Cyclic-group to P-256 bridge: orders agree, generator/target correspond, scalar actions agree
    §5.4: 'The formalization also assumes a correspondence between the generic cyclic group and the P-256 subgroup.'
  • ad hoc to paper The supplied resource and success certificates are valid, including readiness flags
    Listings 3/4 include `retry.readyForFinalStatement = true` and `w.resources.readyForFinalStatement = true` as conjuncts; §B.4 says final statements assemble evidence provided as inputs.
  • ad hoc to paper Each factoring attempt fails with probability at most 1/2 and three attempts are independent
    §4.3: 'The success figure used here assumes that each factoring attempt fails with probability at most one half and that three attempts are independent.'
  • domain assumption One-run resource values from [21] and [7] are correct for the formalized circuits
    Theorems' resource tuples are imported without formal derivation; §6 says 'resource values imported from the literature' enter as explicit assumptions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Building Shor's Algorithm in Lean: An Agentic Formalization of Quantum Attacks on RSA-2048 and P-256." pith.science (2026). https://pith.science/paper/YBZFVBHS

@misc{pith2026260714082,
  author       = {Pith},
  title        = {Pith review of: Building Shor's Algorithm in Lean: An Agentic Formalization of Quantum Attacks on RSA-2048 and P-256},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YBZFVBHS}},
  note         = {Machine review of arXiv:2607.14082}
}
read the original abstract

Large language models are increasingly assisting with demanding formal theorem-proving tasks, particularly when grounded in machine-checked libraries such as Lean. Agentic systems further amplify this process by searching, reusing, and extending existing formal developments to uncover new discoveries. In quantum computing, Shor's algorithm and its variants present such a demanding case for Lean formalization. In this work, we formalize this algorithm family in Lean through agentic formalization: software agents analyze sources, write Lean code and repair proofs, with human review of the scientific claims and machine checking of the resulting formal proofs. Our formalization develops the mathematical foundations for analyzing quantum attacks in two cryptographic settings: a 2048-bit modulus in the RSA-2048 and the standardized elliptic curve over a 256-bit prime field (P-256). To support these analyses, the formalization ranges from quantum algorithms for order finding to reversible quantum circuits for modular and elliptic-curve arithmetic. Based on [Quantum 5, 433] and [ASIACRYPT 2017, 241--270], we formalize the logical resource estimates for RSA-2048 and P-256, respectively, and provide additional estimates of classical operations. We expect the results pave the way for broader machine-checked quantum cryptanalysis and represent a step toward AI-assisted design and verification of quantum algorithms.

Figures

Figures reproduced from arXiv: 2607.14082 by the authors.

Figure 1
Figure 1. An overview of the agentic formalization workflow and its trust boundary. The two rows follow artifacts [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. A dependency map of the Lean development used for the RSA-2048 and P-256 results. Solid arrows [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 4 linked inside Pith

  1. [1]

    Andrew M. Childs. Lecture notes on quantum algorithms, 2021

    2021

  2. [2]

    Quantum computing: Lecture notes, 2019

    Ronald de Wolf. Quantum computing: Lecture notes, 2019

    2019

  3. [3]

    Quantum algorithms: An overview.npj Quantum Information, 2(1):15023, 2016

    Ashley Montanaro. Quantum algorithms: An overview.npj Quantum Information, 2(1):15023, 2016

    2016

  4. [4]

    Lecture notes on quantum algorithms for scientific computation, 2022

    Lin Lin. Lecture notes on quantum algorithms for scientific computation, 2022

    2022

  5. [5]

    Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing, 26(5):1484–1509, 1997

    1997

  6. [6]

    Rivest, Adi Shamir, and Leonard Adleman

    Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM, 21(2):120–126, 1978

    1978

  7. [7]

    Svore, and Kristin Lauter

    Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. InAdvances in Cryptology – ASIACRYPT 2017, volume 10625 ofLecture Notes in Computer Science, pages 241–270. Springer, 2017

    2017

  8. [8]

    Recommendations for discrete logarithm-based cryptography: Elliptic curve domain parameters

    Lily Chen, Dustin Moody, Karen Randall, Andrew Regenscheid, and Angela Robinson. Recommendations for discrete logarithm-based cryptography: Elliptic curve domain parameters. Technical Report NIST Special Publication 800-186, National Institute of Standards and Technology, 2023

    2023

Show all 34 references
  1. [9]

    Quantum factoring, discrete logarithms, and the hidden subgroup problem.Computing in Science & Engineering, 3(2):34–43, 2001

    Richard Jozsa. Quantum factoring, discrete logarithms, and the hidden subgroup problem.Computing in Science & Engineering, 3(2):34–43, 2001

    2001

  2. [10]

    Childs and Wim van Dam

    Andrew M. Childs and Wim van Dam. Quantum algorithms for algebraic problems.Reviews of Modern Physics, 82(1):1–52, 2010

    2010

  3. [11]

    An auto- mated deductive verification framework for circuit-building quantum programs

    Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. An auto- mated deductive verification framework for circuit-building quantum programs. In Nobuko Yoshida, editor, Programming Languages and Systems, pages 148–177, Cham, 2021. Springe...

    2021

  4. [12]

    Quantum hoare logic with classical variables.ACM Transactions on Quantum Computing, 2(4):16:1–16:43, December 2021

    Yuan Feng and Mingsheng Ying. Quantum hoare logic with classical variables.ACM Transactions on Quantum Computing, 2(4):16:1–16:43, December 2021

    2021

  5. [13]

    Qafny: A quantum-program verifier

    Liyi Li, Mingwei Zhu, Rance Cleaveland, Alexander Nicolellis, Yi Lee, Le Chang, and Xiaodi Wu. Qafny: A quantum-program verifier. In Jonathan Aldrich and Guido Salvaneschi, editors,38th European Conference on Object-Oriented Programming (ECOOP 2024), volume 313 ofLeibniz Inter...

    2024

  6. [14]

    A formally certified end-to-end implementation of shor’s factorization algorithm.Proceedings of the National Academy of Sciences, 120(21):e2218775120, May 2023

    Yuxiang Peng, Kesha Hietala, Runzhou Tao, Liyi Li, Robert Rand, Michael Hicks, and Xiaodi Wu. A formally certified end-to-end implementation of shor’s factorization algorithm.Proceedings of the National Academy of Sciences, 120(21):e2218775120, May 2023

    2023

  7. [15]

    The Lean mathematical library

    The mathlib Community. The Lean mathematical library. InProceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, pages 367–381. Association for Computing Machinery, 2020

    2020

  8. [16]

    CSLib: The Lean computer science library, 2026

    Clark Barrett, Swarat Chaudhuri, Fabrizio Montesi, Jim Grundy, Pushmeet Kohli, Leonardo de Moura, Alexandre Rademaker, and Sorrachai Yingchareonthawornchai. CSLib: The Lean computer science library, 2026. 13 Lean-QuantumAlg QudeLeap Research

    2026

  9. [17]

    Lean-QIT: Towards a formal infrastructure for quantum information theory, 2026

    Chengkai Zhu, Ziao Tang, Guocheng Zhen, Yimeng Cao, Yusheng Zhao, Ranyiliu Chen, Xuanqiang Zhao, Lei Zhang, and Xin Wang. Lean-QIT: Towards a formal infrastructure for quantum information theory, 2026

    2026

  10. [18]

    Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan J

    Kaiyu Yang, Aidan M. Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan J. Prenger, and Anima Anandkumar. LeanDojo: Theorem proving with retrieval-augmented language models. InAdvances in Neural Information Processing Systems, volume 36, 2023

    2023

  11. [19]

    Quantum algorithms for computing short discrete logarithms and factoring RSA integers

    Martin Ekerå and Johan Håstad. Quantum algorithms for computing short discrete logarithms and factoring RSA integers. InPost-Quantum Cryptography, volume 10346 ofLecture Notes in Computer Science, pages 347–363. Springer, 2017

    2017

  12. [20]

    An agentic formalization for certified quantum neural network design, 2026

    Mingrui Jing, Lei Zhang, Yusheng Zhao, Hongshun Yao, and Xin Wang. An agentic formalization for certified quantum neural network design, 2026

    2026

  13. [21]

    How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.Quantum, 5:433, 2021

    Craig Gidney and Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.Quantum, 5:433, 2021

  14. [22]

    Shor’s discrete logarithm quantum algorithm for elliptic curves, 2004

    John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves, 2004

    2004

  15. [23]

    Floyd–hoare logic for quantum programs.ACM Transactions on Programming Languages and Systems, 33(6):19:1–19:49, 2011

    Mingsheng Ying. Floyd–hoare logic for quantum programs.ACM Transactions on Programming Languages and Systems, 33(6):19:1–19:49, 2011

    2011

  16. [24]

    A practical quantum hoare logic with classical variables, I.Information and Computation, 309:105417, 2026

    Mingsheng Ying. A practical quantum hoare logic with classical variables, I.Information and Computation, 309:105417, 2026

    2026

  17. [25]

    The Coq proof assistant (8.20), 2024

    The Coq Development Team. The Coq proof assistant (8.20), 2024

    2024

  18. [26]

    CoqQ: Foundational verification of quantum programs.Proceedings of the ACM on Programming Languages, 7(POPL):833– 865, 2023

    Li Zhou, Gilles Barthe, Pierre-Yves Strub, Junyi Liu, and Mingsheng Ying. CoqQ: Foundational verification of quantum programs.Proceedings of the ACM on Programming Languages, 7(POPL):833– 865, 2023

    2023

  19. [27]

    Quantum algorithms revisited

    Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998

    1969

  20. [28]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition edition, 2010

    2010

  21. [29]

    Quantum networks for elementary arithmetic operations.Physical Review A, 54(1):147–153, 1996

    Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum networks for elementary arithmetic operations.Physical Review A, 54(1):147–153, 1996

    1996

  22. [30]

    How to factor 2048 bit RSA integers with less than a million noisy qubits, 2025

    Craig Gidney. How to factor 2048 bit RSA integers with less than a million noisy qubits, 2025. arXiv:2505.15917

    arXiv

  23. [31]

    Hockings, Nouédyn Baspin, Felix Thomsen, Samuel C

    Paul Webster, Lucas Berent, Omprakash Chandra, Evan T. Hockings, Nouédyn Baspin, Felix Thomsen, Samuel C. Smith, and Lawrence Z. Cohen. The pinnacle architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes, 2026. arXiv:2602.11457

    arXiv

  24. [32]

    Madelyn Cain, Qian Xu, Robbie King, Lewis R. B. Picard, Harry Levine, Manuel Endres, John Preskill, Hsin-Yuan Huang, and Dolev Bluvstein. Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits, 2026. arXiv:2603.28627

    2026 arXiv

  25. [33]

    Improved quantum circuits for elliptic curve discrete logarithms

    Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken. Improved quantum circuits for elliptic curve discrete logarithms. InPost-Quantum Cryptography, volume 12100 of Lecture Notes in Computer Science, pages 425–444. Springer, 2020

    2020

  26. [34]

    Space-efficient quantum algorithm for elliptic curve discrete logarithms with resource estimation, 2026

    Han Luo, Ziyi Yang, Ziruo Wang, Yuexin Su, and Tongyang Li. Space-efficient quantum algorithm for elliptic curve discrete logarithms with resource estimation, 2026. arXiv:2604.02311. 14 Lean-QuantumAlg QudeLeap Research Fig 1: An overview of the agentic formalization workflow ...

    arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.