Integer factorization

The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers.

Many cryptographic protocols are based on the presumed difficulty of factoring large composite integers or a related problem—for example, the RSA problem.

An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.

In 2019, a 240-digit (795-bit) number (RSA-240) was factored by a team of researchers including Paul Zimmermann, utilizing approximately 900 core-years of computing power.

No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a b-bit number n in time O(bk) for some constant k. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist.

As of 2022[update], the algorithm with best theoretical asymptotic running time is the general number field sieve (GNFS), first published in 1993,[6] running on a b-bit number n in time: For current computers, GNFS is the best published algorithm for large n (more than about 400 bits).

For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time.

In 2001, Shor's algorithm was implemented for the first time, by using NMR techniques on molecules that provide seven qubits.

An answer of "yes" can be certified by exhibiting a factorization n = d(⁠n/d⁠) with d ≤ k. An answer of "no" can be certified by exhibiting the factorization of n into distinct primes, all larger than k; one can verify their primality using the AKS primality test, and then multiply them to obtain n. The fundamental theorem of arithmetic guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both UP and co-UP.

In addition, there are several probabilistic algorithms that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error.

The ease of primality testing is a crucial part of the RSA algorithm, as it is necessary to find large prime numbers to start with.

In number theory, there are many integer factoring algorithms that heuristically have expected running time in little-o and L-notation.

Another such algorithm is the class group relations method proposed by Schnorr,[11] Seysen,[12] and Lenstra,[13] which they proved only assuming the unproved generalized Riemann hypothesis.

The Schnorr–Seysen–Lenstra probabilistic algorithm has been rigorously proven by Lenstra and Pomerance[14] to have expected running time Ln[⁠1/2⁠, 1+o(1)] by replacing the GRH assumption with the use of multipliers.

The algorithm uses the class group of positive binary quadratic forms of discriminant Δ denoted by GΔ.

Lenstra and Pomerance show that the choice of d can be restricted to a small set to guarantee the smoothness result.