Papex

Open problem · Computer science · Open

Complexity of integer factorisation

Can a classical computer find the prime factors of a large number in polynomial time?

Summary

The security of RSA and similar schemes rests on factoring being hard. The best known classical algorithms are super-polynomial and Shor’s quantum algorithm is polynomial, but no proof rules out a fast classical method.

AI-assisted claims

Partial result claimed · 29 Oct 2026

Deterministic Factoring in Time $N^{o(1)}$

“The current best upper bound for deterministic factoring is $N^{1/5+o(1)}$. We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every $N$ in $N^{o(1)}$ steps: for every $k\ge 1$ it runs within $C_k\,2^{n/k}$ steps on $n$-bit inputs.”

By
Isaac Rudich, Louis-Martin Rousseau
AI involvement
Text declaration: A mix of human-written and AI-generated. Human-understanding declaration: Some parts of this contribution, but not all, have been checked and understood by a human.
Model
Lean 4.35.0; Anthropic Claude Opus 5.5, as stated
Where
Hexagon
Source last read
04 Nov 2026

Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.

All AI-assisted claims

Why it is open

"Polynomial time" here means a number of steps bounded by a fixed polynomial in the number of digits of N, not in N itself. Scott Aaronson describes a decision version, Fac: given N and k, does N have a nontrivial divisor no larger than k? A polynomial-time algorithm for Fac can be turned into one that outputs the full prime factorisation, and vice versa [2].

Fac lies in NP, the class of problems whose "yes" answers have certificates that can be checked quickly: a divisor is such a certificate. It also lies in co-NP, because a "no" answer is certified by the unique prime factorisation of N with every prime larger than k [2]. Checking that those numbers are prime is fast: primality testing has been known to be in P since 2002 [2]. In 1979 Gilles Brassard gave evidence that the security of cryptosystems based on one-way functions would be hard to prove: a proof of NP-completeness for the cryptanalytic effort "would imply NP=CoNP" [3]. In Aaronson's general form, if any problem in both NP and co-NP is NP-complete, then NP = co-NP; factoring is therefore not NP-complete unless NP = co-NP, and Aaronson counts it among problems believed to lie strictly between P and the NP-complete problems, if they are not simply in P [2] (see the Papex pages NP versus co-NP and P versus NP).

A resolution would be a classical polynomial-time algorithm or a proof that none exists. The two outcomes differ in reach: because Fac is in NP, a proof that it needs more than polynomial time would also prove P ≠ NP [2]. No prize or committee sets a bar. This page's status follows the Wikipedia list of unsolved problems in computer science, which asks the question for "a classical (non-quantum) computer" [15], because Peter Shor showed in 1994 that a quantum computer could factor in polynomial time [1].

What is known

Conjectured and proved running times (1992–2021). Running times for factoring are often written as L_N(a, c) = exp(c (log N)^a (log log N)^(1−a)), between polynomial (a = 0) and exponential (a = 1) in the number of digits [4]. The general number field sieve (GNFS), used for the largest factoring records [7], is conjectured to run in time L_N(1/3, (64/9)^(1/3)) raised to the power 1 + o(1) [4, 5]. The authors of the 2020 records write that the 1 + o(1) "reveals a significant lack of accuracy in this complexity estimate" [5]. Proved bounds are weaker. In 1992 Hendrik Lenstra and Carl Pomerance gave a probabilistic algorithm that factors any N in expected time at most L_N(1/2, 1 + o(1)), the first algorithm for which such a bound "can be rigorously proved"; they noted that this "does not close the gap" with the number field sieve [4]. For deterministic algorithms, David Harvey proved in 2021 a bound of N^(1/5 + o(1)) bit operations, after Markus Hittmeir's N^(2/9 + o(1)) and an N^(1/4 + o(1)) bound "going back to the 1970s" [6].

Records (2020–2026). Numbers from the RSA Factoring Challenge serve as benchmarks for the feasibility of breaking the RSA cryptosystem [7]. Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored the 240-digit RSA-240 in about 1,000 core-years and, in February 2020, the 250-digit RSA-250 in roughly 2,700 core-years, using the open-source CADO-NFS software [5, 7]. On 3 September 2026 Eric Lu of the company Cognition completed the factorisation of the 260-digit RSA-260 with a GPU implementation of the GNFS "prepared and run using Devin", Cognition's autonomous software-engineering agent, at an estimated 4,900 GPU-days; he reports "essentially no algorithmic advancements" [7]. On 19 September 2026 Stephen Weis reported factoring RSA-896, a 270-digit number, after using Claude to port CADO-NFS to GPUs; the run took about 30 GPU-years over ten days on up to 2,048 GPUs, and he writes that it did not meaningfully improve the running time of the GNFS [8]. Both 2026 results were announced in blog posts, not in peer-reviewed papers [7, 8].

Quantum context (1994–2025). Shor's algorithms factor integers and compute discrete logarithms on a "hypothetical quantum computer" in a number of steps polynomial in the input size [1] (see Complexity of the discrete logarithm). Aaronson draws two conclusions: if factoring is hard for classical computers, then quantum computers can solve some problems efficiently that randomised classical ones cannot (BPP ≠ BQP); and Shor's method exploits "extremely special properties" of factoring that are not known or believed to hold for NP-complete problems [2]. John Smolin, Graeme Smith and Alexander Vargo showed in 2013 that a "compiled" version of Shor's algorithm can factor products of two large primes with only two coherent qubits; they argued that the right measure of difficulty is the length of the period found, not the size of the number [9]. For full-scale machines, Craig Gidney and Martin Ekerå estimated, in a paper published in 2021, that a 2048-bit RSA integer could be factored in 8 hours with 20 million noisy qubits, assuming, among other things, a physical gate error rate of 0.1% [10]. In a May 2025 preprint, not peer reviewed, Gidney estimated less than a week with less than a million noisy qubits under the same assumptions [12]. In December 2024 Google Quantum AI reported a quantum memory below the surface-code error threshold: a distance-7 code on 101 qubits of its Willow processor, with 0.143% error per cycle, which it says "could realize the operational requirements" of large fault-tolerant algorithms "if scaled" [11].

Recent claims. In December 2022 Bao Yan and colleagues posted a preprint that combines classical lattice reduction with a quantum approximate optimisation algorithm (QAOA); they factored integers of up to 48 bits with 10 superconducting qubits and estimated that 372 physical qubits would be "necessary to challenge RSA-2048" [13]. Sergey Grebnev and colleagues replied in IEEE Access in 2023 that the proposal "lacks systematic analysis of the computational complexity of the classical part of the algorithm", which relies on Claus Peter Schnorr's lattice-based approach [14]. On 15 October 2026 the preprint listed no journal publication [13], and the Wikipedia list still included the question [15].

Main approaches

Faster sieving. Improve the number field sieve and its implementation. Strongest evidence: careful parameter choices and techniques such as batch smoothness detection made the 2020 computations "significantly faster" than extrapolation from earlier records suggested [5], and GPU implementations have since factored larger challenge numbers [7, 8]. Main difficulty: the conjectured L(1/3) form stated in 1992 [4] is the one used for the 2020 records [5], and the authors of both 2026 records report no algorithmic advance [7, 8].

Proved running times. Prove bounds for classical algorithms instead of relying on heuristic estimates. Strongest evidence: a probabilistic L(1/2, 1 + o(1)) bound proved without assuming the generalised Riemann hypothesis [4], and deterministic exponents lowered from 1/4 to 2/9 to 1/5 [6]. Main difficulty: the gap to the conjectured L(1/3) remains [4], and the deterministic bound N^(1/5 + o(1)) is still exponential in the number of digits [6].

Lattice methods. Use classical lattice reduction, as in Schnorr's lattice-based approach, possibly assisted by a small quantum processor [13, 14]. Strongest evidence: Yan and colleagues report factoring integers of up to 48 bits with lattice reduction combined with QAOA [13]. Main difficulty: Grebnev and colleagues argue that the cost of the classical lattice part has not been analysed systematically and give examples of the further resources it needs [14].

Quantum algorithms. Shor's algorithm settles the quantum version of the question [1], so the open issue there is building the machine. Strongest evidence: resource estimates for 2048-bit numbers fell from 20 million noisy qubits (published 2021) to under a million (2025 preprint) [10, 12]. Main difficulty: the 2025 estimate assumes up to a million noisy qubits running for days, while Google's 2024 below-threshold memory used 101 [11, 12]; and a quantum algorithm does not answer the classical question [15].

Open sub-questions

  1. Proving the sieve's running time. Can a randomised algorithm be proved to factor in time L_N(1/3, c) for some constant c, closing the gap that Lenstra and Pomerance described in 1992 [4, 5]?
  2. Deterministic exponent. Is there a deterministic algorithm that provably factors N in N^c bit operations for some c below 1/5 [6]?
  3. Records against the formula. After normalising for hardware, how do the reported costs of RSA-240, RSA-250, RSA-260 and RSA-896 compare with extrapolation from L_N(1/3, (64/9)^(1/3)), and how much of the difference comes from parameter choice [5, 7, 8]?
  4. Lattice relations at scale. For which sizes of N, if any, does the classical lattice part of the method of Yan and colleagues cost less than the number field sieve, once the lattice problems it must solve are counted [13, 14]?
  5. Uncompiled demonstrations. What is the longest period found so far by an uncompiled implementation of Shor's algorithm, the measure of difficulty Smolin and colleagues propose [9]?
  6. From memory to arithmetic. Which components of Gidney's 2025 construction, such as yoked surface codes and magic state cultivation, have been demonstrated on hardware below the error threshold, as Google's 2024 memory was [11, 12]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509. 10.1137/S0097539795293172 · Checked 15 Oct 2026
  2. Aaronson, S. (2016). P =? NP. In Open Problems in Mathematics, Springer, 1–122. 10.1007/978-3-319-32162-2_1 · Checked 15 Oct 2026
  3. Brassard, G. (1979). A note on the complexity of cryptography. IEEE Transactions on Information Theory 25(2), 232–233. 10.1109/TIT.1979.1056010 · Checked 15 Oct 2026
  4. Lenstra, H. W. & Pomerance, C. (1992). A rigorous time bound for factoring integers. Journal of the American Mathematical Society 5(3), 483–516. 10.1090/S0894-0347-1992-1137100-0 · Checked 15 Oct 2026
  5. Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E. & Zimmermann, P. (2020). Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In Advances in Cryptology – CRYPTO 2020, Lecture Notes in Computer Science 12171, Springer, 62–91. 10.1007/978-3-030-56880-1_3 · Checked 15 Oct 2026
  6. Harvey, D. (2021). An exponent one-fifth algorithm for deterministic integer factorisation. Mathematics of Computation 90(332), 2937–2950. 10.1090/mcom/3658 · Checked 15 Oct 2026
  7. Lu, E. (2026). Factoring RSA-260. Cognition blog, 9 September 2026. Source · Checked 15 Oct 2026
  8. Weis, S. A. (2026). RSA-896. Personal website, September 2026. Source · Checked 15 Oct 2026
  9. Smolin, J. A., Smith, G. & Vargo, A. (2013). Oversimplifying quantum factoring. Nature 499(7457), 163–165. 10.1038/nature12290 · Checked 15 Oct 2026
  10. Gidney, C. & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433. 10.22331/q-2021-04-15-433 · Checked 15 Oct 2026
  11. Google Quantum AI and Collaborators (Acharya, R. et al.) (2025). Quantum error correction below the surface code threshold. Nature 638(8052), 920–926 (published online 9 December 2024); author correction 2026 to the labels of Fig. 3a. 10.1038/s41586-024-08449-y · Checked 15 Oct 2026
  12. Gidney, C. (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits. Preprint, arXiv:2505.15917 (version 1, 21 May 2025), not peer reviewed. Source · Checked 15 Oct 2026
  13. Yan, B., Tan, Z., Wei, S., Jiang, H., Wang, W., Wang, H. et al. (2022). Factoring integers with sublinear resources on a superconducting quantum processor. Preprint, arXiv:2212.12372 (version 1, 23 December 2022), not peer reviewed. Source · Checked 15 Oct 2026
  14. Grebnev, S. V., Gavreev, M. A., Kiktenko, E. O., Guglya, A. P., Efimov, A. R. & Fedorov, A. K. (2023). Pitfalls of the sublinear QAOA-based factorization algorithm. IEEE Access 11, 134760–134768. 10.1109/ACCESS.2023.3336989 · Checked 15 Oct 2026
  15. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026

Page reviewed 15 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing