Integer factorization

Integer factorization is the problem of decomposing a composite integer into its prime factors, for example writing a large number as a product of two primes. Multiplying primes is fast, but recovering them from the product is believed hard on classical computers when the factors are large, and no efficient classical algorithm is known. This asymmetry is the hardness assumption behind widely deployed public-key cryptography.

#Cryptographic role and quantum status

The difficulty of factoring a public modulus is the basis of the RSA cryptosystem, whose modulus is a product of two large secret primes; RSA-based key establishment is specified in NIST SP 800-56B. The best known classical method, the general number field sieve, runs in sub-exponential but super-polynomial time, so key sizes grew over the decades to stay ahead of it. That defense collapses against quantum computing: Shor's algorithm factors integers in polynomial time on a large fault-tolerant quantum computer, the same algorithm that solves the Discrete logarithm problem problem. Its eventual availability is the core motivation for Post-quantum cryptography.