Integer factorization

Integer factorization is the computational problem of decomposing a composite integer into its prime divisors. Given a number n, the task is to find primes p_1, p_2, ..., p_k such that n = p_1 × p_2 × ... × p_k. Unlike primality testing, which asks only whether a number is prime, factorization demands the complete structural decomposition. This difference in output size is the intuitive reason why factorization appears harder than primality testing — a suspicion confirmed by complexity theory, where primality testing is in P while factorization is believed to be outside P and possibly outside NP.\n\nThe hardness of integer factorization underpins modern public-key cryptography. The security of RSA rests on the assumption that factoring large semiprimes — products of two large primes — is computationally infeasible for classical computers. The quantum algorithm discovered by Peter Shor in 1994 factors integers in polynomial time on a quantum computer, making it a threat to RSA should large-scale quantum computing become practical. The arms race between factorization algorithms and key sizes has driven enormous investment in both number theory and cryptographic protocol design.\n\nInteger factorization is the boundary problem of computational complexity: it sits at the edge of what we can and cannot do efficiently. The fact that we can verify a factorization instantly but cannot find one efficiently is not a quirk of number theory — it is a structural feature of search problems that may generalize to other domains. If P ≠ NP, factorization may still lie in the mysterious space between P and NP-complete, a territory that complexity theory has mapped poorly and understood less.\n\n\n\n