up:: Classical Cryptography MOC

integer factorization

Integer factorization is the problem of taking a large whole number and finding the prime numbers that were multiplied together to produce it. Multiplying two large primes is fast and easy; working backward from the product to recover those primes is believed to be so slow on a classical computer that it protects real secrets. That one-way difficulty is the hardness assumption RSA is built on, which is why factoring is one of the most consequential math problems in all of cryptography. The load-bearing fact for the post-quantum era is simple: a large enough quantum computer running Shor’s algorithm factors these numbers in polynomial time, so RSA breaks completely the day such a machine exists.

The short version:

• Multiplying is easy, factoring is hard. Anyone can multiply two big primes in an instant; recovering them from the product is the slow direction that keeps the private key private.
• RSA rests entirely on this one assumption. An RSA public key is a number n that’s secretly the product of two primes, and factoring n hands an attacker the private key.
• The best classical attack is sub-exponential. The General Number Field Sieve is the fastest known method, slower than an easy polynomial-time problem but too slow to crack real key sizes, so an 829-bit number still took thousands of CPU-core-years to factor in 2020.
• Shor’s algorithm collapses the difficulty. On a fault-tolerant quantum computer it factors in polynomial time, which is a total break of RSA at every key size, not a weakening.
• The discrete logarithm problem is the other Shor-vulnerable assumption. Diffie-Hellman, ECDH, and ECDSA rest on it, and Shor breaks it too, which is why the entire classical public-key family falls together.

Think of a large number as a smoothie. Blending two specific fruits together is quick and anyone can do it, but if you’re handed only the finished smoothie and asked to name the exact two fruits that went in, you’re stuck tasting and guessing. Factoring a cryptographic number is that guessing problem at enormous scale, where the “fruits” are two prime numbers hundreds of digits long. A classical computer has no shortcut, so it grinds through the search. Shor’s algorithm is a quantum shortcut that tastes every possibility at once, and the moment that shortcut is buildable, the smoothie gives up its ingredients.

What is the integer factorization problem?

The integer factorization problem is: given a composite (non-prime) whole number n, find the prime numbers that multiply together to produce it. Every whole number greater than 1 has exactly one prime factorization, a fact so fundamental it’s called the Fundamental Theorem of Arithmetic, so the answer always exists and is unique. The difficulty is purely in finding it. For the small numbers people meet in school this is trivial, but for the specially chosen numbers used in cryptography it becomes one of the hardest computations known.

In the cryptographic case the number has a deliberate structure. An RSA modulus n is built as n = p × q, where p and q are two large, randomly chosen prime numbers kept secret. Recovering p and q from n is the exact instance of the factorization problem that matters, and it’s the whole game. Whoever factors n can reconstruct the RSA private key and read or forge anything that key protected.

Cryptographers usually separate two closely related problems. The first is the Integer Factorization Problem itself, recovering the primes of n. The second is the RSA Problem, undoing an RSA operation without knowing the factorization. Factoring n always solves the RSA Problem, and no easier general shortcut than factoring is known, so in practice RSA’s security is treated as standing or falling on factoring.

Source: R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 1978, ACM.

How hard is factoring for a classical computer?

Factoring is hard classically because the best known algorithms run in sub-exponential time, fast enough to make progress but far too slow to break cryptographic key sizes. The fastest published general-purpose method is the General Number Field Sieve (GNFS). Its heuristic running time grows on the order of exp((1.923 + o(1))(ln n)^(1/3)(ln ln n)^(2/3)), a curve that mathematicians call sub-exponential because it sits between polynomial (easy) and fully exponential (hopeless). That middle ground is exactly why RSA worked for decades: the effort to factor rises steeply with key size, so the defender can pick a size where the attacker’s cost is astronomical.

Source: A. K. Lenstra and H. W. Lenstra, Jr. (eds.), “The Development of the Number Field Sieve,” Lecture Notes in Mathematics 1554, Springer, 1993, Springer.

The public record of factoring records shows how steep that cost is in practice. In February 2020 a team led by Fabrice Boudot factored RSA-250, an 829-bit number, using the Number Field Sieve. The computation consumed roughly 2,700 CPU-core-years spread across tens of thousands of machines, and it was one of the largest factoring efforts ever completed. RSA-250 is smaller than the RSA-2048 keys still guarding production systems, which underscores the gap: the state-of-the-art classical attack, given a global compute effort, still lands well short of the sizes deployed everywhere.

Source: F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, and P. Zimmermann, “Factorization of RSA-250,” announcement, February 28, 2020, caramba.loria.fr.

The takeaway for a defender is that classical factoring gets harder faster than it gets easier. Every added bit of key length costs an attacker far more than it costs the defender, which is the arithmetic that made RSA a safe bet for half a century, right up until a fundamentally different kind of computer entered the picture.

Why does integer factorization matter for cryptography?

Integer factorization matters because it’s the single assumption holding up RSA, and RSA sits at the root of an enormous amount of the trust on the internet. RSA does two core jobs: it carries or wraps keys so two parties can share a secret, and it produces the digital signatures that anchor PKI and the certificate chains behind the padlock in a browser. Both jobs rest on the same bet, that nobody can factor the modulus. Take away that bet and both jobs fail at once.

The dependency is direct and unavoidable in the way RSA is constructed:

1. An RSA key pair is generated from two secret primes p and q, whose product n becomes the public modulus.
2. The private key is derived from p and q (specifically from (p − 1)(q − 1)), so knowing the primes is equivalent to knowing the private key.
3. Anyone who factors the public n back into p and q can recompute the private key and then decrypt ciphertext or forge signatures at will.

This is why “factoring is hard” and “RSA is secure” are the same sentence. It’s also why the vulnerability is structural rather than something a patch can fix. There’s no configuration, padding scheme, or vendor setting that changes the fact that RSA’s security is an assumption about factoring, and if that assumption ever falls, every RSA deployment inheriting it falls with it.

How does a quantum computer break integer factorization?

A quantum computer breaks factoring by running Shor’s algorithm, which solves the integer factorization problem in polynomial time instead of sub-exponential time. Peter Shor published the result in 1994 and detailed it in 1997, and it’s the reason RSA is the textbook casualty of quantum computing. Where the classical attacker’s cost explodes with key size, Shor’s cost grows only gently, so a machine large enough to factor a cryptographic key doesn’t need to be much larger to factor a bigger one.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, SIAM.

The break, once the hardware exists, runs in a straight line:

1. The attacker takes the RSA public key, which includes the modulus n.
2. A cryptographically relevant quantum computer runs Shor’s algorithm and factors n into its primes p and q.
3. From p and q, the private key falls out with ordinary arithmetic, and the attacker can now decrypt and forge everything that key covered.

This is a complete structural break, not a partial weakening. It’s also why enlarging the key does nothing to save RSA: Shor’s resource cost scales polynomially with the number of bits, so a bigger modulus adds qubits and runtime to the attack without putting it out of reach. The published estimates make the shape concrete. Gidney and Ekerå estimated in 2021 that factoring a 2048-bit RSA key would take on the order of 20 million noisy qubits running for about 8 hours, and a 2025 estimate brought that figure to under a million qubits. No machine at that scale exists yet, but the direction of those numbers is why the migration is happening now.

Sources: C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, Quantum; C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv.

One clean distinction to keep: Grover’s algorithm, the other famous quantum attack, does nothing to factoring. Grover gives a quadratic speedup on brute-force search, which matters for symmetric ciphers like AES, but it has no purchase on the number-theoretic structure of factoring. The break of RSA comes from Shor and Shor alone.

How is integer factorization different from the discrete logarithm problem?

Integer factorization and the discrete logarithm problem (DLP) are two different hard problems, but they share one fatal property: Shor’s algorithm solves both in polynomial time. That shared weakness is why the whole classical public-key family falls together rather than one algorithm at a time. Factoring underpins RSA. The discrete logarithm problem underpins Diffie-Hellman key exchange, ECDH, and the ECDSA signatures used across TLS and blockchains. Different math, same quantum executioner.

The reason Shor breaks both is that factoring and discrete log are both instances of a deeper structure called the hidden subgroup problem over a commutative group, which Shor’s period-finding machinery is built to solve. Shor’s original 1997 paper is titled for exactly this pairing, “Prime Factorization and Discrete Logarithms,” because the two results came together. So a defender who migrates away from RSA but leaves elliptic-curve cryptography in place has traded one Shor-vulnerable assumption for another, which is why post-quantum migration replaces the entire classical public-key layer rather than swapping within it.

Property	Integer factorization	Discrete logarithm problem
The hard task	Recover primes p, q from n = p × q	Recover exponent x from g^x in a group
Algorithms that rest on it	RSA	Diffie-Hellman, ECDH, ECDSA
Best classical attack	General Number Field Sieve (sub-exponential)	Index calculus / Pollard’s rho (sub-exponential to exponential)
Broken by Shor’s algorithm?	Yes, polynomial time	Yes, polynomial time
Post-quantum status	Fully replaced, not resized	Fully replaced, not resized

The practical rule is that both problems belong to the quantum-vulnerable set and both get retired together. The discrete logarithm problem has its own note for the detail; the point here is that neither is a post-quantum answer, and a real migration treats them as one job.

How does the quantum transition affect factoring-based cryptography?

The quantum transition retires factoring-based cryptography entirely, replacing it rather than tuning it, because no factoring key size survives Shor’s algorithm. NIST finalized the replacements on August 13, 2024. For the key-exchange job RSA used to do, the successor is ML-KEM, a lattice-based key-encapsulation mechanism whose security rests on lattice problems that no known quantum algorithm breaks. For signatures, the successors are ML-DSA and the conservative hash-based SLH-DSA. None of these depend on factoring or discrete logs, which is the entire point.

Source: NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards,” August 13, 2024, NIST.

NIST’s transition schedule reflects the finality of the break. Its guidance deprecates RSA-2048 after 2030 and disallows the quantum-vulnerable public-key algorithms after 2035, treating factoring-based cryptography as an algorithm to sunset rather than a parameter to keep raising.

Source: NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, NIST.

There’s a timing wrinkle that makes this urgent well before any quantum computer switches on: harvest now, decrypt later. An adversary can record RSA-protected traffic today and simply store it until a CRQC can factor the key. Anything that must stay confidential past the machine’s eventual arrival is exposed the moment it crosses an RSA-protected channel, so the practical clock on factoring-based confidentiality started years ago.

Common misconceptions

• “Factoring is easy, computers do it all the time.” Small numbers factor instantly, but the specially built products of two large primes used in RSA are the hard case, and the best classical method still needs thousands of CPU-core-years for numbers smaller than deployed keys.
• “A bigger RSA key fixes the quantum problem.” Enlarging the key defends only against classical factoring. Shor’s algorithm scales polynomially with key size, so a 4096-bit key is no safer against a quantum computer than a 2048-bit one, which is why NIST replaces RSA rather than resizing it.
• “Quantum computers break all encryption by breaking factoring.” They break the public-key half through Shor’s attack on factoring and discrete logs. Symmetric ciphers like AES rest on no such structure, and Grover’s algorithm only halves their strength, so they survive with a larger key.
• “RSA and elliptic-curve crypto rely on the same hard problem.” They don’t. RSA rests on integer factorization, elliptic-curve algorithms on the discrete logarithm problem. They’re different assumptions, but Shor’s algorithm breaks both, so migrating from one to the other buys no post-quantum safety.
• “If nobody has factored RSA-2048, it’s safe forever.” Classical safety today says nothing about quantum safety tomorrow. The threat model is a future quantum computer plus data harvested now, so a key unbroken today can still expose data that’s being recorded today.
• “Factoring being hard is a proven fact.” It’s a well-tested assumption, not a theorem. No one has proven factoring must be hard classically, and Shor’s algorithm already proves it is not hard on a quantum computer.

Questions people ask

What is integer factorization in simple terms? It’s the problem of finding which prime numbers multiply together to make a given number. Multiplying the primes is easy, but reversing the process to recover them from the product is extremely slow for the large numbers used in cryptography, and that difficulty is what protects an RSA private key.

Why is factoring hard for a computer? Because the fastest known general algorithm, the General Number Field Sieve, runs in sub-exponential time, so the effort climbs steeply as the number gets bigger. Cracking an 829-bit number took roughly 2,700 CPU-core-years in 2020, and standard RSA keys are 2048 bits or larger, well beyond reach of any classical effort so far.

Does a quantum computer make factoring easy? It makes it dramatically easier. Shor’s algorithm factors in polynomial time on a fault-tolerant quantum computer, collapsing a problem that’s astronomically hard classically into one that’s tractable. No machine capable of factoring a real RSA key exists yet, but published estimates put the requirement at under a million qubits, and hardware estimates keep shrinking.

What does factoring have to do with RSA? Everything. An RSA public key is a number that’s secretly the product of two primes, and the private key is derived from those primes. Anyone who can factor the public number recovers the primes and therefore the private key, so breaking factoring breaks RSA completely.

Is the discrete logarithm problem the same thing as factoring? No, they’re different hard problems, but they share a fatal weakness. Factoring underpins RSA; the discrete logarithm problem underpins Diffie-Hellman, ECDH, and ECDSA. Shor’s algorithm solves both in polynomial time, which is why the whole classical public-key family is retired together.

If factoring gets broken, what replaces RSA? NIST-standardized post-quantum algorithms that rest on different math. ML-KEM (FIPS 203) replaces RSA’s key-exchange role and ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) replace its signature role, all finalized in August 2024. None of them depend on factoring or discrete logs, so Shor’s algorithm doesn’t touch them.

Has anyone actually factored a real RSA key? Not a currently deployed one. The largest RSA challenge number factored classically is RSA-250 (829 bits) in 2020, and RSA-2048 remains unfactored by any classical or quantum method. The concern is forward-looking: a future quantum computer combined with data harvested today.

Do I need to understand factoring to plan a migration? Not the math, but the consequence. The one fact that drives decisions is that factoring is the assumption RSA depends on, and a quantum computer breaks that assumption at every key size, so RSA and its cousins get replaced rather than reconfigured.

---

Everything here is the map, given freely. When your team needs its own factoring-dependent cryptography found, classified, and sequenced for replacement, that’s what an alignment briefing is for.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.