Integer factorization

Integer factorization is the decomposition of a composite integer into a product of smaller integers, ideally prime factors. For the products of two large primes — semiprimes — this problem is believed to be computationally intractable for classical computers, a belief that underpins the security of the RSA algorithm and much of the world's digital infrastructure.

The problem's asymmetry is stark: multiplying two primes is trivial; recovering them from their product is, as far as we know, extraordinarily difficult. Shor's algorithm demonstrated that this asymmetry is not fundamental but computational: a quantum computer could factor efficiently. The search for faster classical algorithms — from the General Number Field Sieve to hypothetical polynomial-time methods — is therefore not merely a mathematical sport. It is a probe into the boundary between what classical and quantum computation can achieve.