In number theory, integer factorization or prime factorization is the breaking down of a composite number into smaller nontrivial divisors, which when multiplied together equal the original integer.
When the numbers are very large, no efficient integer factorization algorithm is publicly known; an effort concluded in 2009 by several researchers factored a 232digit number (RSA768) utilizing hundreds of machines over a span of 2 years.^{[1]} The presumed difficulty of this problem is at the heart of certain algorithms in cryptography such as RSA. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing.
Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, randomly chosen, and about the same size (but not too close), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical.
Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem, the RSA problem. An algorithm which efficiently factors an arbitrary integer would render RSAbased publickey cryptography insecure.
Contents
Prime decomposition
By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (A special case for 1 is not needed using an appropriate notion of the empty product.) However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.
Given an algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm.
Current state of the art
Full article ▸
