
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 32·5. The factorization is always unique, according to the fundamental theorem of arithmetic. This problem is of significance in mathematics, cryptography, computational complexity theory, and quantum computer. ==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 = 32·51, 45 is divisible by 30·50, 30·51, 31·50, 31·51, 32·50, and 32·51, 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 Big O notation(''n''''k'') for any constant ''k''. There are algorithms, however, that are faster than Big O notation(e''n''). 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: : 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''3) time and O(''n'') space. Forms of the algorithm are known that use only about 2''n'' 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 computational complexity theory 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 (complexity) 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 complexity classes P and NP, 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 * William%27s_p_plus_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. [http://citeseer.nj.nec.com/327036.html download] *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 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 [http://indigo.ie/~mscott/ MIRACL] * [http://www.alpertron.com.ar/ECM.HTM 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. * [http://www.rsasecurity.com/rsalabs/node.asp?id=2093 The RSA Challenge Numbers] - a factoring challenge. Number theoryInteger factorization algorithms
I thought Diffie-Hellman required calculating logarithms on a finite field, not factorisation, or are the problems somehow related? ----- Yes Diffie-Hellman is discrete logarithm. So is DSA. Discrete logarithm for integers modulo a prime appears to be related somehow it factorisation, but a factorisation breakthrough is not guaranteed to solve discrete logarithm. The current champion method of both problems is the Number Field Seive, and there are only minor differences between the version that does factors and the version that does discrete logarithm. Also Shor's algorithm (which works on proposed quantum computers: no-one knows if they can actually be built large enough to be useful) would blow both problems out of the water. But there is no guarantee (as far as we know at the moment) that a breakthrough factoring algorithm would also do discrete logarithm. I'm not sure if a breakthrough discrete log method is guaranteed to do factoring as well. Several otherwise reputable people have claimed that it would, but i have never seen a proof, or a cite of one. ----- Yes, that's right. I wasn't thinking when I typed the list. I'll remove the DH/DSS entries. --user:LC ----- Actually i don't know a lot about BBS, but i rather suspect it would be difficult to break if you don't know the modulus. So even if factorisation is easy, if you don't tell people the modulus, BBS might be safe. Does anyone know if this is true? I vaguely remember there are some proposed uses of BBS where you do tell people the modulus, so a quick factor method would at least reduce the usefulness of BBS. ----- If the discrete log problem can be solved quickly, factorization can also be done quickly.. this has been proven. As for the BBS. Breaking BBS is provably as hard as factoring the Modulus. If you had a huge modulus and it was secret then i guess it'd be incredibly hard to break. ---- The article says: :This problem is of significance in mathematics, cryptography, complexity theory, and quantum computers. Is it really of significance "in" complexity theory and quantum computers? I would interpret this as meaning that a deeper understanding of integer factorization would lead to a deeper understanding of complexity theory (or quantum computers). I'm not sure that this is true (unlike the case for mathematics or cryptography). == Article name == I was just wondering... Should this be at prime factorization? That term seems to be more common. -- User:Oliver Pereira 04:25, 7 Jan 2004 (UTC) :It's rather difficult to say...this article was named "integer factorization" because there are other types of factorization (you can factorize polynomials, for example). I'd say either is OK, so "integer factorization" should stand, I think. User:Decrypt3 01:05, Jul 30, 2004 (UTC) :Besides, ''prime factorization'' is certain to draw fire from Wikipedians pointing out that primes cannot be factorized.
—User:Herbee 18:30, 18 Feb 2005 (UTC) :No, "prime factorization" is understood to mean decomposing integers into primes. It's a recognized term: [http://mathworld.wolfram.com/PrimeFactorization.html]. User:Decrypt3 21:20, Feb 18, 2005 (UTC) ::Granted, but being wrong never seems to inhibit do-gooders from flaming or "being bold". I think ''integer factorization'' is slightly better than ''prime factorization'' because it draws less fire. —User:Herbee 15:26, 2005 May 23 (UTC) ---- Is the recently added external link by 136.1.1.154 really necessary? It doesn't really aid comprehension of the topic, and to be honest, I find it to be an insult to the reader's intelligence. User:Decrypt3 01:09, Jul 30, 2004 (UTC) : I agree it's not particularly useful; I've removed it. User:Matt Crypto 01:19, 30 Jul 2004 (UTC) ---- There is a separate and unnecessary article called prime factorization algorithm that should be deleted. I don't see anything worthy of merging there. Anyone cares to volunteer? :I vote to delete. All it is, is an extended example of trial division. If anything, the example and source code should be merged into trial division. User:Decrypt3 21:20, Feb 18, 2005 (UTC) == Prime factorization is in P == ... not unknown as this article suggests. See prime numbers. == Factorization record == Perhaps I'm being too pedantic, but the article says :As of 2005, the largest number factored using general-purpose methods... Surely this is misleading? Large numbers that are p-smooth number for small p can be factored in polynomial time, so should it be made clear that it is really the record for factoring semiprimes that is mentioned? User:Birkett 11:22, 21 May 2005 (UTC) ::You're right. That edit was incorrect; I've reverted it. User:Decrypt3 16:39, May 21, 2005 (UTC) ::: My original thinking was that the clause "using general methods as part of public research" covered it for all numbers, because has anyone factored a larger number using general methods as part of public research? You could easily generate such a record, of course. Perhaps we need a better qualifier than "as part of public research"? User:Matt Crypto 21:57, 22 May 2005 (UTC) ::: Now I'm thinking that maybe the "general-purpose methods" part should go. We use semiprimes as the gauge of factoring technology because they're the most "difficult", but in theory, the fact that they're semiprimes doesn't matter for general-purpose algorithms, by definition. I think larger numbers have been factored, but using specialized algorithms because they're not semiprimes. I think only the semiprimes are really relevant here because of their application in public-key crypto. So I think the general-purpose part is causing the problem. User:Decrypt3 08:09, May 23, 2005 (UTC)
See other meanings of words starting from letter:
Words begining with Integer_factorization:
Integer_factorization
Integer_factorization
Integer_factorization_algorithms
Integer_factorization_problem
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 32·5. The factorization is always unique, according to the fundamental theorem of arithmetic. This problem is of significance in mathematics, cryptography, computational complexity theory, and quantum computer. ==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 = 32·51, 45 is divisible by 30·50, 30·51, 31·50, 31·51, 32·50, and 32·51, 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 Big O notation(''n''''k'') for any constant ''k''. There are algorithms, however, that are faster than Big O notation(e''n''). 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: : 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''3) time and O(''n'') space. Forms of the algorithm are known that use only about 2''n'' 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 computational complexity theory 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 (complexity) 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 complexity classes P and NP, 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 * William%27s_p_plus_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. [http://citeseer.nj.nec.com/327036.html download] *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 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 [http://indigo.ie/~mscott/ MIRACL] * [http://www.alpertron.com.ar/ECM.HTM 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. * [http://www.rsasecurity.com/rsalabs/node.asp?id=2093 The RSA Challenge Numbers] - a factoring challenge. Number theoryInteger factorization algorithms
Integer factorization
I thought Diffie-Hellman required calculating logarithms on a finite field, not factorisation, or are the problems somehow related? ----- Yes Diffie-Hellman is discrete logarithm. So is DSA. Discrete logarithm for integers modulo a prime appears to be related somehow it factorisation, but a factorisation breakthrough is not guaranteed to solve discrete logarithm. The current champion method of both problems is the Number Field Seive, and there are only minor differences between the version that does factors and the version that does discrete logarithm. Also Shor's algorithm (which works on proposed quantum computers: no-one knows if they can actually be built large enough to be useful) would blow both problems out of the water. But there is no guarantee (as far as we know at the moment) that a breakthrough factoring algorithm would also do discrete logarithm. I'm not sure if a breakthrough discrete log method is guaranteed to do factoring as well. Several otherwise reputable people have claimed that it would, but i have never seen a proof, or a cite of one. ----- Yes, that's right. I wasn't thinking when I typed the list. I'll remove the DH/DSS entries. --user:LC ----- Actually i don't know a lot about BBS, but i rather suspect it would be difficult to break if you don't know the modulus. So even if factorisation is easy, if you don't tell people the modulus, BBS might be safe. Does anyone know if this is true? I vaguely remember there are some proposed uses of BBS where you do tell people the modulus, so a quick factor method would at least reduce the usefulness of BBS. ----- If the discrete log problem can be solved quickly, factorization can also be done quickly.. this has been proven. As for the BBS. Breaking BBS is provably as hard as factoring the Modulus. If you had a huge modulus and it was secret then i guess it'd be incredibly hard to break. ---- The article says: :This problem is of significance in mathematics, cryptography, complexity theory, and quantum computers. Is it really of significance "in" complexity theory and quantum computers? I would interpret this as meaning that a deeper understanding of integer factorization would lead to a deeper understanding of complexity theory (or quantum computers). I'm not sure that this is true (unlike the case for mathematics or cryptography). == Article name == I was just wondering... Should this be at prime factorization? That term seems to be more common. -- User:Oliver Pereira 04:25, 7 Jan 2004 (UTC) :It's rather difficult to say...this article was named "integer factorization" because there are other types of factorization (you can factorize polynomials, for example). I'd say either is OK, so "integer factorization" should stand, I think. User:Decrypt3 01:05, Jul 30, 2004 (UTC) :Besides, ''prime factorization'' is certain to draw fire from Wikipedians pointing out that primes cannot be factorized.
—User:Herbee 18:30, 18 Feb 2005 (UTC) :No, "prime factorization" is understood to mean decomposing integers into primes. It's a recognized term: [http://mathworld.wolfram.com/PrimeFactorization.html]. User:Decrypt3 21:20, Feb 18, 2005 (UTC) ::Granted, but being wrong never seems to inhibit do-gooders from flaming or "being bold". I think ''integer factorization'' is slightly better than ''prime factorization'' because it draws less fire. —User:Herbee 15:26, 2005 May 23 (UTC) ---- Is the recently added external link by 136.1.1.154 really necessary? It doesn't really aid comprehension of the topic, and to be honest, I find it to be an insult to the reader's intelligence. User:Decrypt3 01:09, Jul 30, 2004 (UTC) : I agree it's not particularly useful; I've removed it. User:Matt Crypto 01:19, 30 Jul 2004 (UTC) ---- There is a separate and unnecessary article called prime factorization algorithm that should be deleted. I don't see anything worthy of merging there. Anyone cares to volunteer? :I vote to delete. All it is, is an extended example of trial division. If anything, the example and source code should be merged into trial division. User:Decrypt3 21:20, Feb 18, 2005 (UTC) == Prime factorization is in P == ... not unknown as this article suggests. See prime numbers. == Factorization record == Perhaps I'm being too pedantic, but the article says :As of 2005, the largest number factored using general-purpose methods... Surely this is misleading? Large numbers that are p-smooth number for small p can be factored in polynomial time, so should it be made clear that it is really the record for factoring semiprimes that is mentioned? User:Birkett 11:22, 21 May 2005 (UTC) ::You're right. That edit was incorrect; I've reverted it. User:Decrypt3 16:39, May 21, 2005 (UTC) ::: My original thinking was that the clause "using general methods as part of public research" covered it for all numbers, because has anyone factored a larger number using general methods as part of public research? You could easily generate such a record, of course. Perhaps we need a better qualifier than "as part of public research"? User:Matt Crypto 21:57, 22 May 2005 (UTC) ::: Now I'm thinking that maybe the "general-purpose methods" part should go. We use semiprimes as the gauge of factoring technology because they're the most "difficult", but in theory, the fact that they're semiprimes doesn't matter for general-purpose algorithms, by definition. I think larger numbers have been factored, but using specialized algorithms because they're not semiprimes. I think only the semiprimes are really relevant here because of their application in public-key crypto. So I think the general-purpose part is causing the problem. User:Decrypt3 08:09, May 23, 2005 (UTC)
See other meanings of words starting from letter:
I
IA | IB | IC | ID | IE | IF | IG | IH | IJ | IK | IL | IM | IN | IO | IP | IR | IS | IT | IU | IW | IX | IY | IZ |Words begining with Integer_factorization:
Integer_factorization
Integer_factorization
Integer_factorization_algorithms
Integer_factorization_problem
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
