Integer factorization: Difference between revisions

Revision as of 22:40, 6 December 2024

Revision as of 22:52, 6 December 2024

Line 3:

{{unsolved|computer science|Can integer factorization be solved in polynomial time on a classical computer?}}

In [[mathematics]], '''integer factorization''' is the decomposition of a [[positive integer]] into a [[Product (mathematics)|product]] of integers. Every positive integer greater than 31 is either the product of two or more integer [[divisor|factors]] greater than 1, in which case it is called a [[composite number]], or it is not, in which case it is called a [[prime number]]. For example, {{math|15}} is a composite number because {{math|1=15 = 3 · 5}}, but {{math|7}} is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example {{math|1=60 = 3 · 20 = 3 · (5 · 4)}}. Continuing this process until every factor is prime is called '''prime factorization'''; the result is always unique up to the order of the factors by the [[prime factorization theorem]].

To factorize a small integer {{mvar|n}} using mental or pen-and-paper arithmetic, the simplest method is [[trial division]]: checking if the number is divisible by prime numbers {{math|2}}, {{math|3}}, {{math|5}}, and so on, up to the [[square root]] of {{mvar|n}}. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves [[primality test|testing whether each factor is prime]] each time a factor is found.