Integer factorization is believed to be hard, but it has never been proven NP-complete. If it were NP-complete, RSA encryption would collapse the moment P=NP was proven. The fact that factorization sits in an ambiguous middle ground is what makes RSA’s security simultaneously credible and theoretically unresolved after 50 years.
Pithy Cyborg | AI FAQs – The Details
Question: Why is integer factorization not proven to be NP-complete — and why does that matter for encryption?
Asked by: Claude Sonnet 4.6
Answered by: Mike D (MrComputerScience)
From Pithy Cyborg | AI News Made Simple
And Pithy Security | Cybersecurity News
What NP-Complete Actually Means and Why Factorization Misses the Bar
NP-complete problems have two properties: they are in NP (solutions can be verified quickly), and every other NP problem can be reduced to them in polynomial time. That second property is the hard part. Proving a problem NP-complete requires constructing a polynomial-time reduction from every NP problem to yours.
Integer factorization is clearly in NP. Given a number N and a claimed factor p, you can verify p divides N in milliseconds. That part is easy.
The NP-completeness proof has never materialized because nobody has successfully reduced all NP problems to factorization. More importantly, most complexity theorists believe factorization is probably not NP-complete at all. The strongest evidence is that factorization is also in co-NP: if a number is prime, you can verify that quickly too. Problems that sit in both NP and co-NP are unlikely to be NP-complete, because proving one NP-complete would collapse the polynomial hierarchy, a result considered far more surprising than P=NP alone.
So factorization lives in a murky middle: hard enough that no efficient classical algorithm is known, but probably not the hardest problem in NP.
Why RSA’s Security Rests on an Unproven Assumption
RSA encryption works because multiplying two large primes together is fast, while factoring the result back into those primes appears to be slow. The operative word is “appears.” RSA security is not mathematically proven. It is an empirical bet that has held for 47 years.
The best classical factoring algorithm today is the General Number Field Sieve. It runs in sub-exponential time, faster than brute force but slower than any polynomial algorithm. For a 2048-bit RSA key, factoring would require more computing power than humanity currently has access to. That is a practical guarantee, not a theoretical one.
This distinction matters enormously. If P=NP were proven tomorrow, NP-complete problems would become tractable and a huge portion of modern cryptography would break immediately. RSA might or might not break depending on exactly where factorization falls in the complexity landscape. The fact that factorization is probably not NP-complete means RSA could theoretically survive a P=NP proof, though nobody is counting on that.
What actually threatens RSA is not complexity theory but Shor’s algorithm. A fault-tolerant quantum computer running Shor’s algorithm factors integers in polynomial time. This is why quantum-wrapping RSA-2048 emails is an active engineering problem today, not a theoretical future concern.
How This Ambiguity Shapes Real Cryptographic Decisions in 2026
The unresolved status of factorization’s complexity has pushed the cryptography community toward two parallel responses.
The first is hedging within classical cryptography. Elliptic curve cryptography and lattice-based schemes do not rely on factorization at all. NIST finalized its post-quantum cryptography standards in 2024, standardizing CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures. Both are based on lattice problems that are believed to resist both classical and quantum attacks.
The second is accepting that “computationally hard” is the real security primitive, not “provably intractable.” No widely deployed cryptographic system rests on a proven lower bound. AES has no proof that breaking it requires exponential time. SHA-256 has no proof that finding collisions is hard. Cryptographic security is engineering under uncertainty, not mathematical certainty.
For practical systems in 2026, the guidance from NIST is clear: begin migrating away from RSA and elliptic curve schemes toward post-quantum alternatives now, while RSA remains safe, because migration takes years and harvested ciphertext attacks are already happening.
What This Means For You
- Do not treat RSA as mathematically proven secure. It is an empirical bet on factorization hardness, not a theorem.
- Start tracking NIST’s post-quantum standards. CRYSTALS-Kyber and CRYSTALS-Dilithium are the replacements you will be deploying in the next five years.
- Understand that quantum computers are the real threat to RSA, not a P=NP proof. Shor’s algorithm is the specific mechanism to plan around.
- Audit any system storing encrypted data long-term. Adversaries collecting RSA-encrypted ciphertext today can decrypt it later once quantum hardware matures.
- Stop conflating NP-hard with unbreakable. Complexity class membership is a statement about worst-case inputs, not about the specific numbers your system will encounter.
Pithy Cyborg | AI News Made Simple
Subscribe (Free): https://pithycyborg.substack.com/subscribe
Read archives (Free): https://pithycyborg.substack.com/archive
Pithy Security | Cybersecurity News
Subscribe (Free): https://pithysecurity.substack.com/subscribe
Read archives (Free): https://pithysecurity.substack.com/archive