Integer factorization

In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. For example, given the number 45, the prime factorization would be 3²·5. The factorization is always unique, according to the fundamental theorem of arithmetic. This problem is of significance in mathematics, cryptography, complexity theory, and quantum computing.

Contents

1 Prime decomposition 2 Practical applications 3 Current state of the art 3.1 Difficulty and complexity 4 Factoring algorithms 4.1 Special-purpose 4.2 General-purpose 4.3 Other notable algorithms 5 External links

Prime decomposition

The complete list of factors can be derived from the prime factorization by incrementing the exponents from zero until the number is reached. For example, since 45 = 3²·5¹, 45 is divisible by 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, and 3²·5¹, or 1, 5, 3, 15, 9, and 45. In contrast, the prime factorization only includes prime factors. See prime factorization algorithm.

Practical applications

Given two large prime numbers, it is easy to multiply them together. However, given their product, it appears to be difficult to find the factors. This is relevant for many modern systems in cryptography. If a fast method were found for solving the integer factorization problem, then several important cryptographic systems would be broken, including the RSA public-key algorithm and the Blum Blum Shub pseudo-random number generator.

Although fast factoring is one way to break these systems, there may be other ways to break them that do not involve factoring. So it is possible that the integer factorization problem is truly hard, yet these systems can still be broken quickly. A rare exception is the Blum Blum Shub generator. It has been proved to be exactly as hard as integer factorization: if you can break the generator in polynomial time then you can factorize integers in polynomial time, and vice versa.

Current state of the art

As of 2005, the largest semiprime factored using general-purpose methods as part of public research is RSA-200, which is 663 bits long.

If a large, n-bit number is the product of two primes that are roughly the same size, then no algorithm is known that can factor in polynomial time. That means there is no known algorithm that can factor it in time O(n^k) for any constant k. There are algorithms, however, that are faster than Θ(eⁿ). In other words, the best known algorithms are sub-exponential, but super-polynomial. In particular, the best known asymptotic running time is for the general number field sieve (GNFS) algorithm, which is:

<math>

\Theta\left(\exp\left( \left(\frac{64}{9}n\right)^{\frac{1}{3}} (\log n)^{\frac{2}{3}} \right)\right). <math>

For an ordinary computer, GNFS is the best known algorithm for large n. For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time. This will have significant implications for cryptography if a large quantum computer is ever built. Shor's algorithm takes only O(n³) time and O(n) space. Forms of the algorithm are known that use only about 2n qubits. In 2001, the first 7-qubit quantum computer became the first to run Shor's algorithm. It factored the number 15.

Difficulty and complexity

It is not known exactly which complexity classes contain the integer factorization problem. The decision-problem form of it ("does N have a factor less than M?") is known to be in both NP and co-NP. This is because both YES and NO answers can be checked if given the prime factors along with their primality proofs. It is known to be in BQP because of Shor's algorithm. It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find polynomial-time algorithms for it and failed, therefore it is widely suspected to be outside P.

Interestingly, the decision problem "is N a composite number?" (or equivalently: "is N a prime number?") appears to be much easier than the problem of actually finding the factors of N. Specifically, the former can be solved in polynomial time (in the number n of digits of N), according to a recent preprint given in the references, below. In addition, there are a number of probabilistic algorithms that can test primality very quickly if one is willing to accept the small possibility of error. The easiness 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

Special-purpose

A special-purpose factoring algorithm's running time depends on the properties of its unknown factors: size, special form, etc. Exactly what the running time depends on varies between algorithms.

• Trial division
• Pollard's rho algorithm
• Pollard's p-1 algorithm
• Williams' p+1 algorithm
• Lenstra elliptic curve factorization
• Fermat's factorization method
• Special number field sieve
• Jones's period proxy algorithm

General-purpose

A general-purpose factoring algorithm's running time depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose factoring algorithms are based on the congruence of squares method.

• Dixon's algorithm
• Continued fraction factorization (CFRAC)
• Quadratic sieve
• General number field sieve

Other notable algorithms

• Shor's algorithm, for quantum computers

External links

• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp.3-22. download (http://citeseer.nj.nec.com/327036.html)
• Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002, http://www.cse.iitk.ac.in/news/primality.html
• The "PRIMES is in P" FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
• ftp://ftp.computing.dcu.ie/pub/crypto/factor.exe is a public-domain integer factorization program for Windows. It claims to handle 80-digit numbers. See also the web site for MIRACL (http://indigo.ie/~mscott/)
• http://www.alpertron.com.ar/ECM.HTM is an integer factorization Java applet that uses the Elliptic Curve Method and the Self Initializing Quadratic Sieve.
• The RSA Challenge Numbers (http://www.rsasecurity.com/rsalabs/node.asp?id=2093) - a factoring challenge.de:Primfaktorzerlegung

nl:priemfactor ja:素因数分解 sl:praštevilski razcep zh:整数分解