Among the -bit numbers, the most difficult to factor in practice using existing algorithms are those
semiprimes whose factors are of similar size. For this reason, these are the integers used in cryptographic applications. 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. These researchers estimated that a 1024-bit RSA modulus would take about 500 times as long. The largest such semiprime yet factored was
RSA-250, an 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using Intel
Xeon Gold 6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the
general number field sieve run on hundreds of machines.
Time complexity No
algorithm has been published that can factor all integers in
polynomial time, that is, that can factor a -bit number in time for some constant . Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist. There are published algorithms that are faster than for all positive , that is,
sub-exponential. , the algorithm with best theoretical asymptotic running time is the
general number field sieve (GNFS), first published in 1993, running on a -bit number in time: : \exp\left( \left(\left(\tfrac83\right)^\frac23 + o(1)\right)\left(\log n\right)^\frac13\left(\log \log n\right)^\frac23\right). For current computers, GNFS is the best published algorithm for large (more than about 400 bits). For a
quantum computer, however,
Peter Shor discovered an algorithm in 1994 that solves it in polynomial time.
Shor's algorithm takes only time and space on -bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using
NMR techniques on molecules that provide seven qubits. In order to talk about
complexity classes such as P, NP, and co-NP, the problem has to be stated as a
decision problem. It is known to be in both
NP and
co-NP, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization with . An answer of "no" can be certified by exhibiting the factorization of into distinct primes, all larger than ; one can verify their primality using the
AKS primality test, and then multiply them to obtain . 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. It is known to be in
BQP because of Shor's algorithm. The problem is suspected to be outside all three of the complexity classes P, NP-complete, and
co-NP-complete. It is therefore a candidate for the
NP-intermediate complexity class. In contrast, the decision problem "Is a composite number?" (or equivalently: "Is a prime number?") appears to be much easier than the problem of specifying factors of . The composite/prime problem can be solved in polynomial time (in the number of digits of ) with the
AKS primality test. 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. == Factoring algorithms ==