Multiplying two huge prime numbers is easy. Going backwards, from the product to the two primes, is believed to be extremely hard.
The idea: This is how a hard problem becomes a lock. Pick two big primes, multiply them, and publish the product as part of your public key. Anyone can use the product to scramble a message (RSA), but unscrambling needs a number that can only be computed from the two primes. So the primes are a secret shortcut, a trapdoor: easy for you, who made the product, and, as far as anyone knows, impossible for everyone else unless they factor the product.
Why it matters: RSA, still used in many website certificates, depends on it.
On the map: best attack: number field sieve
Given N = p × q for two large primes, find p and q. Multiplying is easy. Factoring is believed hard for ordinary computers. The best algorithm, the general number field sieve[1], is faster than brute force but still sub-exponential: the public record is an 896-bit number (RSA-896, factored in September 2026 with about 30 GPU-years of computation)[2], and 2048-bit moduli are standard.
Shor's algorithm factors efficiently on a large quantum computer[3]. If factoring becomes easy, RSA, Rabin and Paillier all break. The converse is subtler for RSA: computing its private exponent from the public key is exactly as hard as factoring[4], but whether decrypting without it is remains open. It earns the KE tag because Rabin encryption is provably exactly as hard as factoring[5].
If any of these breaks, this breaks too.
If this breaks, these break with it.